The context-splittable normal form for Church-Rosser language systems
In this paper the context-splittable normal form for rewriting systems defining Church-Rosser languages is introduced. Context-splittable rewriting rules look like rules of context-sensitive grammars with swapped sides. To be more precise, they have the form uvw --> uxw with u, v, w being words, v being nonempty and x being a sin-le letter or the empty word. It is proved that this normal form can be achieved for each Church-Rosser language and that the construction is effective. Some interesting consequences of this characterization are given, too. (C) 2003 Elsevier Science (USA). All rights reserved.
church-rosser languages string-rewriting confluence growing context-sensitive languages