Let a(n) be the number of states of the smallest deterministic finite automaton that reads two Zeckendorf representations in parallel and accepts exactly the pairs (x,y) with val(y)=nval(x), the dead state not counted; this is sequence A372846 of the OEIS.…
Jirásek and Jirásková (arXiv:2511.03814) close their study of the state complexity of the concatenation L₁L₂… Lₖ of k regular languages with the unary case, and give an upper bound for unary automata that may carry final states in their tails: if Aᵢ has siz…
Luo's open-problem note from COLT 2005, reissued in 2026 as arXiv:2605.30389, asks for the inclusion depth ID_Σ(p) of a pattern p — the length of the longest strict chain of pattern-language inclusions joining L_Σ(x₁) to L_Σ(p) — and asks whether ID_Σ(p) =…
For a word x over a finite alphabet, A_(Ne)(x) is the least number of states of a nondeterministic finite automaton that accepts x and no other word of length |x|, and A_(N)(x) is the least number of states of one that in addition accepts x along a single c…
A backtracking regular expression matcher runs in linear time exactly when the underlying memoized automaton has no infinite degree of ambiguity (IDA), and a set of states whose memoization removes IDA is a memoization set. Berglund, van der Merwe and le Ro…
A medium in the sense of Eppstein and Falmagne is a deterministic finite automaton whose letters — its tokens — come in mutually reverse pairs and which satisfies three further axioms; equivalently it is the token system of a well-graded family of sets, and…
Let t(i) be the number of ones in the Zeckendorf representation of i, reduced modulo 2 (the Fibonacci–Thue–Morse sequence, OEIS A095076), and let sc(c) be the number of states of the smallest automaton with output that reads a Zeckendorf representation most…
Let f=f(0)f(1)f(2)…=01001010… be the Fibonacci word and let sc(c) be the number of states of the smallest deterministic finite automaton with output that reads a Zeckendorf representation most-significant-digit first and generates the shifted word (f(i+c))_…
Szykuła's recent survey of open problems on synchronising automata introduces the compress-with-another threshold of a state — the length of a shortest word sending that state and some other state to a common image — and records a conjecture, for a series A…
PCP(w) is the set of Post correspondence instances with two tiles, each tile a pair of nonempty binary words of length at most w. Ling Zhao's 2002 search tabulated, for w ≤ 6, the largest shortest-solution length over the class — the values 2,4,6,8,10 — and…
Lipin and Volkov introduced the mw(m)-synchronization game, in which Alice plays a nonempty word of length at most m and Bob replies with an arbitrary finite word, and proved that an n-state automaton on which Alice wins has a reset word of length at most m…
