The time complexity of 1-limited automata is investigated from a descriptional complexity view point. Though the model recognizes regular languages only, it may use quadratic time in the input length. We show that, with a polynomial increase in size and preserving determinism, each 1-limited automaton can be transformed into an halting linear-time equivalent one. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines, and we show exponential gaps for converse transformations in the deterministic case.

Linear-time limited automata : extended abstract / B. Guillon, L. Prigioniero (CEUR WORKSHOP PROCEEDINGS). - In: Italian Conference on Theoretical Computer Science / [a cura di] A. Aldini, M. Bernardo. - [s.l] : CEUR-WS, 2018. - pp. 208-212 (( Intervento presentato al 19. convegno Italian Conference on Theoretical Computer Science tenutosi a Urbino nel 2018.

Linear-time limited automata : extended abstract

B. Guillon
;
L. Prigioniero
2018

Abstract

The time complexity of 1-limited automata is investigated from a descriptional complexity view point. Though the model recognizes regular languages only, it may use quadratic time in the input length. We show that, with a polynomial increase in size and preserving determinism, each 1-limited automaton can be transformed into an halting linear-time equivalent one. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines, and we show exponential gaps for converse transformations in the deterministic case.
Computer Science (all)
Settore INF/01 - Informatica
http://ceur-ws.org/Vol-2243/paper20.pdf
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
paper20.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 409.58 kB
Formato Adobe PDF
409.58 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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: http://hdl.handle.net/2434/605998
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact