An Iteration Theorem for Simple Precedence Languages
Yael Krevner, Amiram Yehudai · Journal of the ACM · 1983
An iteration theorem for simple precedence languages ts presented.The theorem is then used to prove very easily that certain languages are not simple precedence.In addttion, a strong characterizauon of simple precedence languages is established.This is obtained by analyzing a nontrivlal famdy of languages that includes typical languages which are not stmple precedence languages and some similar languages which are m fact simple precedence.The iterauon theorem is then generahzed to deal with certain families of extended precedence languages Using this theorem, a rs shown that none of the languages proved to be nonstmple precedence is umquely invertible (1, k) precedence for any k _> 1.