Papers for

automata designers

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.

Machines with more power can cause huge size increases in equivalent simpler machines

Non-recursive trade-offs for two-way machines

Abstract: If the machines of some type A have enough resources to (i) solve problems that no machine of type B can solve, and (ii) simulate any unary two-way deterministic finite automaton that has access to a linearly-bounded counter, then typically no recursive function can upper bound the increase in the size of description when a machine of type A is replaced by an equivalent machine of type B.

Thu 8 OctFormal Languages and Automata Theory
The gist
Some types of computing machines are much more powerful than others, meaning they can solve problems the simpler ones can't. The authors find that when you try to convert a powerful machine into a simpler one, the size of the description can explode beyond any predictable limit. This means there is no general way to estimate how big the simpler machine’s description will get. The study focuses on machines that use two-way reading and counters in a very specific way.
Open → 2610.11969v1

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

Improved state complexity lower bound for permutation automata separation

An Improved Lower Bound for Separating Words by Permutation Automata

Abstract: We prove that some pairs of binary words of every sufficiently large prescribed length $n$ require $Ω(\log n\log\log n)$ states to separate by a deterministic finite automaton whose letters act as permutations. We obtain this bound by constructing distinct equal-length positive binary words that form an identity of $\mathfrak{S}_k$ of length $\exp(O(k/\log k))$. This improves the previous lower bound $(3/2-o(1))\log n$ of Bulatov, Karpova, Shur, and Startsev (arXiv:1609.03199). The proof combines a positive-word construction with a cover of permutation orders. Consecutive segments of prime powers reduce the covering problem to enumerating sets of positive integers with bounded sum. The required estimates use the central binomial coefficient and the classical asymptotic formula for partitions into distinct parts. An appendix gives sharper constants and lower-order terms using a greedy cover and a quantitative prime number theorem.

Thu 8 OctFormal Languages and Automata Theory
The gist
Some pairs of binary words need surprisingly big machines to tell them apart when the machines act by rearranging letters in fixed ways. The authors found that this complexity grows faster than previously known, meaning you need even larger machines to separate certain word pairs as the words get longer. They built special word pairs linked to permutations and used number theory tools to prove this stronger requirement. This shows a more difficult limit on the size of these machines than was known before.
Open → 2610.11098v1