Name
Abstract | ||
|---|---|---|
Functional graph grammars are finite devices which generate the class of regular automata. We recall the notion of synchronization by grammars, and for any given grammar we consider the class of languages recognized by automata generated by all its synchronized grammars. The synchronization is an automaton-related notion: all grammars generating the same automaton synchronize the same languages. When the synchronizing automaton is unambiguous, the class of its synchronized languages forms an effective boolean algebra lying between the classes of regular languages and unambiguous context-free languages. We additionally provide sufficient conditions for such classes to be closed under concatenation and its iteration. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03816-7_2 | MFCS |
Keywords | Field | DocType |
sufficient condition,finite device,synchronizing automaton,automaton-related notion,regular automaton,automaton synchronize,functional graph grammar,unambiguous context-free language,regular automata,effective boolean algebra,regular language,context free language,boolean algebra | Context-sensitive grammar,Deterministic context-free grammar,Embedded pushdown automaton,Discrete mathematics,Nondeterministic finite automaton,Context-free grammar,Nested word,Computer science,Abstract family of languages,Indexed language,Theoretical computer science | Conference |
Volume | ISSN | Citations |
5734 | 0302-9743 | 3 |
PageRank | References | Authors |
0.42 | 9 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Didier Caucal | 1 | 470 | 39.15 |