Aufsatz in einer Fachzeitschrift
The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages



Details zur Publikation
Autor(inn)en:
Niemann, G.; Otto, F.
Publikationsjahr:
2005
Zeitschrift:
Information and Computation
Seitenbereich:
1-21
Jahrgang/Band:
197
ISSN:
0890-5401

Zusammenfassung, Abstract
The growing context-sensitive languages have been classified through the shrinking two-pushdown automaton, the deterministic version of which characterizes the class of generalized Church-Rosser languages [Inform. Comput. 141 (1998) 1]. Exploiting this characterization we prove that the latter class coincides with the class of Church-Rosser languages that was introduced by McNaughton et al. [J. ACM 35 (1988) 324]. Based on this result several open problems of McNaughton et al. are solved. In addition, we show that shrinking two-pushdown automata and length-reducing two-pushdown automata are equivalent, both in the non-deterministic and the deterministic case, thus obtaining still another characterization of the growing context-sensitive languages and the Church-Rosser languages, respectively. (c) 2004 Elsevier Inc. All rights reserved.


Autor(inn)en / Herausgeber(innen)

Zuletzt aktualisiert 2019-01-11 um 16:04