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.
EnglishLimited automata are one-tape Turing machines that can rewrite the contents of tape cells only in the first d visits, for a fixed d. When d=1 these models characterize regular languages. We show an exponential gap between the size of limited automata accepting unary languages and the size of equivalent finite automata. Despite this gap, there are unary regular languages for which d-limited automata cannot be significantly smaller than finite automata, for any arbitrarily large d. We also prove that from each unary context-free grammar G it is possible to obtain an equivalent 1-limited automaton whose description has a size that is polynomial in the size of G. For alphabets of cardinality at least 2, for each grammar G generating a context-free language L, it is possible to obtain a 1-limited automaton whose description has polynomial size in that of G and whose accepted language L ′ is Parikh-equivalent to L.
| Titolo: | Limited automata and unary languages |
| Autori: | PRIGIONIERO, LUCA (Corresponding) |
| Parole Chiave: | Unary languages; Limited automata; Context-free grammars; Parikh equivalence |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 2019 |
| Rivista: | |
| Tipologia: | Article (author) |
| Digital Object Identifier (DOI): | 10.1016/j.ic.2019.01.002 |
| Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| la_and_unary_languages.pdf | Publisher's version/PDF | Administrator Richiedi una copia |
http://hdl.handle.net/2434/642422
Copyright © 2019