Generalization of the Ginsburg-Rice Schützenberger fixed-point theorem for context-sensitive and recursive-enumerable languages

AbstractThe paper generalizes the Ginsburg-Rice Schützenberger ALGOL-like fixed-point theorem showing that every λ-free context-sensitive (recursive-enumerable) language is a component of the least fixed-point of a system of equations in the form X = F(X), where X = (X1,…,Xt), F = (F1,…,Ft),t⩾1 and for all i, 1⩽i⩽t, Fi are regular expre ssions over the alphabet of operations: {union, concatenation, Kleene+ (∗) closure, nonerasing finite substitution (arbitrary finite substitution), intersection}.Fixed-point characterization theorems for these families of languages are also presented