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.
Titolo: | Linear-time limited automata : extended abstract |
Autori: | PRIGIONIERO, LUCA (Corresponding) |
Parole Chiave: | Computer Science (all) |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2018 |
URL: | http://ceur-ws.org/Vol-2243/paper20.pdf |
Tipologia: | Book Part (author) |
Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
paper20.pdf | Publisher's version/PDF | Administrator Richiedi una copia |