Name
Abstract | ||
|---|---|---|
Deterministic graph grammars are finite devices which gen- erate 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 effec- tive 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-79709-8_14 | Computer Science Symposium in Russia |
Keywords | Field | DocType |
sufficient condition,finite device,pushdown automaton,grammar form,deterministic context-free language,deterministic graph grammar,effective boolean algebra,regular language,previous sub-classes,height-deterministic pushdown automaton,context free language,pushdown automata,boolean algebra | Deterministic context-free grammar,Context-sensitive grammar,Tree-adjoining grammar,Discrete mathematics,Embedded pushdown automaton,Context-free language,Nested word,Computer science,Deterministic pushdown automaton,Deterministic context-free language | Conference |
Volume | ISSN | ISBN |
5010 | 0302-9743 | 3-540-79708-4 |
Citations | PageRank | References |
7 | 0.52 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Didier Caucal | 1 | 470 | 39.15 |
| Stéphane Hassen | 2 | 7 | 0.52 |