CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe 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.
http://hdl.handle.net/2108/52718| Autori interni: | GIAMMARRESI, DORA VARRICCHIO, STEFANO |
| 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 |
File in questo prodotto:
Copyright © 2017