Paper Info
Title
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 a linear-time equivalent one. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines (i.e., one-tape Turing machines syntactically forced to operate in linear-time), and we show exponential gaps for the converse transformations in the deterministic case.
Year
DOI
Venue
2019
10.1016/j.tcs.2019.03.037
Theoretical Computer Science
Keywords
DocType
Volume
Regular languages,Limited automata,Descriptional complexity
Journal
798
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Bruno Guillon121.39
Luca Prigioniero202.03