Limited 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.
Limited automata and unary languages / G. Pighizzini, L. Prigioniero. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 266(2019), pp. 60-74.
Limited automata and unary languages
G. Pighizzini
;L. Prigioniero
2019
Abstract
Limited 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.File | Dimensione | Formato | |
---|---|---|---|
la_and_unary_languages.pdf
accesso aperto
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
183.1 kB
Formato
Adobe PDF
|
183.1 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S0890540119300021-main.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
479.18 kB
Formato
Adobe PDF
|
479.18 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.