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 / B. Guillon, L. Prigioniero (LECTURE NOTES IN COMPUTER SCIENCE). - In: Descriptional Complexity of Formal Systems / [a cura di] S. Konstantinidis G. Pighizzini. - [s.l] : Springer Verlag, 2018. - ISBN 9783319946306. - pp. 126-138 (( Intervento presentato al 20. convegno International Conference on Descriptional Complexity of Formal Systems tenutosi a Halifax nel 2018 [10.1007/978-3-319-94631-3_11].
Linear-time limited automata
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
lt1la.pdf
accesso riservato
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
345.27 kB
Formato
Adobe PDF
|
345.27 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.
