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.
Unary languages; Limited automata; Context-free grammars; Parikh equivalence
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/642422
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact