Journal article

Publication year: 2018

Pages: 259-276

Journal: Information and Computation

Volume number: 259

ISSN: 0890-5401

eISSN: 1090-2651

Open access status: Green

DOI Link: https://doi.org/10.1016/j.ic.2017.09.005

Publisher: Elsevier

Abstract: 
A k-limited automaton is a linear bounded automaton that may rewrite each tape cell only in the first k visits, where k >= 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate the descriptional complexity of limited automata. Since the unary languages accepted are necessarily regular, we first study the cost in the number of states when finite automata simulate a unary k-limited automaton. For the conversion of a 4n-state deterministic 1-limited automaton into one-way or two-way deterministic or nondeterministic finite automata, we show a lower bound of n . F(n) states, where F denotes Landau's function. So, even the ability to deterministically rewrite any cell only once gives an enormous descriptional power. For the simulation cost for removing the ability to rewrite each cell k >= 1 times, more precisely, the cost for the simulation of sweeping unary k-limited automata by deterministic finite automata, we obtain a lower bound of n . F(n)(k). The upper bound of the cost for the simulation by two-way deterministic finite automata is a polynomial whose degree is quadratic in k. If the k-limited automaton is rotating, the upper bound reduces to O(n(k+1)) and the lower bound derived is Omega(n(k+1)) even for nondeterministic two-way finite automata. So, for rotating k-limited automata, the trade-off for the simulation is tight in the order of magnitude. Finally, we consider the simulation of k-limited automata over general alphabets by pushdown automata. It turns out that the cost is an exponential blow-up of the size. Furthermore, an exponential size is also necessary. (c) 2017 Elsevier Inc. All rights reserved.

Harvard Citation style: Kutrib, M., Pighizzini, G. and Wendlandt, M. (2018) Descriptional complexity of limited automata, Information and Computation, 259, pp. 259-276. https://doi.org/10.1016/j.ic.2017.09.005

APA Citation style: Kutrib, M., Pighizzini, G., & Wendlandt, M. (2018). Descriptional complexity of limited automata. Information and Computation. 259, 259-276. https://doi.org/10.1016/j.ic.2017.09.005