IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishWe define a complexity measure on context-free grammars called end. Roughly speaking, for a context-free grammar G, endG(n) measures the distance of variables from the ends of sentential forms along the derivations of words in L(G) of length n. We prove in a constructive way the regularity of L(G) whenever endG(n) is constant. Yet, we improve on this by showing that if L(G) is nonregular then endG(n) = Ω∞(log n). Finally, the optimality of such a lower bound is established.
http://hdl.handle.net/2434/40310| Titolo: | A regularity condition for context-free grammars |
| Autori interni: | PALANO, BEATRICE SANTA (Primo) |
| Parole Chiave: | Complexity measures; Context-free grammars |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 2007 |
| Tipologia: | Book Part (author) |
| Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
| File | Descrizione | Dimensione | Formato | Tipologia | Licenza | |
|---|---|---|---|---|---|---|
| dcfs07.pdf | 162.53 kB | Adobe PDF | Post-print (versione accettata dall'editore) | Administrator Richiedi una copia |
Copyright © 2017