Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages.

Limited automata and context-free languages / G. Pighizzini, A. Pisoni. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 136:1-2(2015), pp. 157-176. ((Intervento presentato al 5. convegno NCMA Workshop on Non-Classical Models of Automata and Applications: August, 13th - 14th tenutosi a Umea (Sweden) nel 2013.

Limited automata and context-free languages

G. Pighizzini
Primo
;
2015

Abstract

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages.
descriptional complexity; deterministic context-free languages; finite automata; formal languages; Turing machines;
Settore INF/01 - Informatica
Umea University
Article (author)
File in questo prodotto:
File Dimensione Formato  
fulltext.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 380.84 kB
Formato Adobe PDF
380.84 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
ncmaJournalFinal.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 445.31 kB
Formato Adobe PDF
445.31 kB Adobe PDF Visualizza/Apri
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/266278
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 20
social impact