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.
EnglishNon-self-embedding grammars, constant-height pushdown automata and 1-limited automata are restrictions of context-free grammars, pushdown automata and Turing machines, respectively. All of them characterize the class of regular languages. There is a double size exponential gap from each of these models to deterministic finite automata. Non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Moreover, there exists a polynomial size simulation by 1-limited automata. In contrast, the converse transformation costs exponential.
On some succinct representations of regular languages : extended abstract / B. Guillon, G. Pighizzini, L. Prigioniero (CEUR WORKSHOP PROCEEDINGS). - In: Italian Conference on Theoretical Computer Science / [a cura di] A. Aldini, M. Bernardo. - [s.l] : CEUR-WS, 2018. - pp. 203-207 (( Intervento presentato al 19. convegno Italian Conference on Theoretical Computer Science tenutosi a Urbino nel 2018.
| Titolo: | On some succinct representations of regular languages : extended abstract |
| Autori: | PRIGIONIERO, LUCA (Corresponding) |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 2018 |
| URL: | http://ceur-ws.org/Vol-2243/paper19.pdf |
| Tipologia: | Book Part (author) |
| Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| paper19.pdf | Publisher's version/PDF | Administrator Richiedi una copia |
Copyright © 2021