Descriptive complexity grows beyond recursive bounds when reducing automaton heads
From k+1 to k heads the descriptive trade-off is non-recursive
Formal Languages and Automata Theory
Summary
The paper finds that if you try to simplify a computer model called a two-way deterministic finite automaton by using fewer 'heads' to read input, the complexity of describing it can explode unpredictably. In fact, no computable function can predict how much more complicated the description gets. This applies even if the models are limited to one-letter alphabets or allow guessing (nondeterminism). The authors proved this for all numbers of heads, showing a fundamental limitation in how these models can be simplified.
What this means in practice
- •For automata designers: Know that reducing the number of heads in two-way deterministic finite automata can cause unbounded increases in description size, limiting simplification strategies.
- •For compiler optimization teams: Understand inherent limits in compressing multi-head automaton models for program analysis and optimization tasks due to non-recursive growth in descriptions.
A theory result. No direct application yet.
Authors
Christos Kapoutsis
Abstract
We prove that no recursive function can upper bound the increase in the size of description when a two-way deterministic finite automaton with k+1 heads is replaced by an equivalent two-way deterministic finite automaton with k heads. This is true for all k, and remains true if the automata are unary and/or nondeterministic.