Linear-Time Limited Automata

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905632
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:22 AM
Last modification on : Monday, March 25, 2019 - 5:08:02 PM
Long-term archiving on : Sunday, January 27, 2019 - 12:59:40 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Bruno Guillon, Luca Prigioniero. Linear-Time Limited Automata. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.126-138, ⟨10.1007/978-3-319-94631-3_11⟩. ⟨hal-01905632⟩

Share

Metrics

Record views

40