%0 Conference Proceedings
%T Linear-Time Limited Automata
%+ Università degli Studi di Milano = University of Milan (UNIMI)
%A Guillon, Bruno
%A Prigioniero, Luca
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 20th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Halifax, NS, Canada
%Y Stavros Konstantinidis
%Y Giovanni Pighizzini
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10952
%P 126-138
%8 2018-07-25
%D 2018
%R 10.1007/978-3-319-94631-3_11
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01905632/document
%2 https://inria.hal.science/hal-01905632/file/470153_1_En_11_Chapter.pdf
%L hal-01905632
%U https://inria.hal.science/hal-01905632
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10952