zbMATH — the first resource for mathematics

Synchronization of grammars. (English) Zbl 1142.68413
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 110-121 (2008).
Summary: Deterministic graph grammars are finite devices which generate the transition graphs of pushdown automata. We define the notion of synchronization by grammars, generalizing previous sub-classes such as visibly and height-deterministic pushdown automata. The languages recognized by grammars synchronized by a given grammar form an effective boolean algebra lying between regular languages and deterministic context-free languages. We also provide a sufficient condition to obtain the closure under concatenation and its iteration.
For the entire collection see [Zbl 1136.68005].

68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
PDF BibTeX Cite
Full Text: DOI