Quantcast

Descriptional complexity of limited automata

Research paper by MartinKutriba, GiovanniPighizzinib, MatthiasWendlandta

Indexed on: 11 Nov '17Published on: 01 Sep '17Published in: Information and Computation



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<math class="math"><mi is="true">k</mi><mo is="true">≥</mo><mn is="true">0</mn></math> 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)<math class="math"><mi is="true">n</mi><mo is="true">⋅</mo><mi is="true">F</mi><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><mo stretchy="false" is="true">)</mo></math> 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<math class="math"><mi is="true">k</mi><mo is="true">≥</mo><mn is="true">1</mn></math> 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<math class="math"><mi is="true">n</mi><mo is="true">⋅</mo><mi is="true">F</mi><msup is="true"><mrow is="true"><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><mo stretchy="false" is="true">)</mo></mrow><mrow is="true"><mi is="true">k</mi></mrow></msup></math>. 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(nk+1)<math class="math"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mi is="true">k</mi><mo is="true">+</mo><mn is="true">1</mn></mrow></msup><mo stretchy="false" is="true">)</mo></math> and the lower bound derived is Ω(nk+1)<math class="math"><mi mathvariant="normal" is="true">Ω</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mi is="true">k</mi><mo is="true">+</mo><mn is="true">1</mn></mrow></msup><mo stretchy="false" is="true">)</mo></math> 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.