Skip to Main content Skip to Navigation
Conference papers

Synchronization of grammars

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620185
Contributor : Didier Caucal <>
Submitted on : Monday, September 30, 2013 - 7:42:08 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Tuesday, December 31, 2013 - 2:40:34 AM

File

synchro.pdf
Files produced by the author(s)

Identifiers

Citation

Didier Caucal, Stéphane Hassen. Synchronization of grammars. Third International Computer Science Symposium in Russia (CSR'08), Jun 2008, Moscou, Russia. pp.110-121, ⟨10.1007/978-3-540-79709-8_14⟩. ⟨hal-00620185⟩

Share

Metrics

Record views

306

Files downloads

286