The context-splittable normal form for Church–Rosser language systems |
| |
Authors: | Jens R Woinowski |
| |
Affiliation: | TU Darmstadt, Fachbereich Informatik, Wilhelminenstr. 7, 64283, Darmstadt, Germany |
| |
Abstract: | 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 single 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. |
| |
Keywords: | Church– Rosser languages String-rewriting Confluence Growing context-sensitive languages |
本文献已被 ScienceDirect 等数据库收录! |
|