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. When d >= 2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call strongly limited automata, where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa.

Strongly limited automata / G. Pighizzini. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 148:3-4(2016), pp. 369-392. [10.3233/FI-2016-1439]

Strongly limited automata

G. Pighizzini
Primo
2016

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. When d >= 2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call strongly limited automata, where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa.
context-free languages; forgetting automata
Settore INF/01 - Informatica
2016
Article (author)
File in questo prodotto:
File Dimensione Formato  
fi%2F2016%2F148-3-4%2Ffi-148-3-4-fi1439%2Ffi-148-fi1439.pdf

accesso riservato

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

accesso aperto

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