Papers for

compiler optimization teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Descriptive complexity grows beyond recursive bounds when reducing automaton heads

From k+1 to k heads the descriptive trade-off is non-recursive

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.

Thu 8 OctFormal Languages and Automata Theory
The gist
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.
Open → 2610.11958v1