We consider non-self-embedding (NSE) context-free grammars as a representation of regular sets. We point out its advantages with respect to more classical representations by finite automata, in particular when considering the efficient realization of the rational operations. We give a characterization in terms of composition of regular grammars and state relationships between NSE grammars and push-down automata. Finally we show a polynomial algorithm to decide whether a context-free grammars is self-embedding or not.
Anselmo M., G.D. (2003). Finite automata and non-self-embedding grammars. In IMPLEMENTATION AND APPLICATION OF AUTOMATA (pp.47-56). SPRINGER-VERLAG BERLIN.
Autori: | |
Autori: | Anselmo M., Giammarresi D., Varricchio S. |
Titolo: | Finite automata and non-self-embedding grammars |
Nome del convegno: | 7th International Conference on Implementation and Application of Automata |
Luogo del convegno: | TOURS, FRANCE |
Anno del convegno: | JUL 03-05, 2002 |
Enti collegati al convegno: | Xerox Res Ctr Europe, CNRS, Univ Tours, EATCS, ACM, SIGACT |
Rilevanza: | Rilevanza internazionale |
Sezione: | contributo |
Data di pubblicazione: | 2003 |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Lingua: | English |
Tipologia: | Intervento a convegno |
Citazione: | Anselmo M., G.D. (2003). Finite automata and non-self-embedding grammars. In IMPLEMENTATION AND APPLICATION OF AUTOMATA (pp.47-56). SPRINGER-VERLAG BERLIN. |
Appare nelle tipologie: | 02 - Intervento a convegno |