2026/07/28 by Bjørn Kjos-Hanssen
Computer Science · Mathematics · #cs.FL #math.LO
arxiv created 2026/07/28 · arxiv updated 2026/07/30
Gill (arXiv:2402.13376) introduced the probabilistic automatic complexity AP(w) of a finite string w: the least number of states of a probabilistic finite automaton (PFA) for which w is the unique most probably accepted string of its length. He asked whether AP is unbounded, noting that no string with AP > 3 was known (Question 4.14 of that paper). We answer the question by proving that AP(w)≤ 3 for every string w over every finite alphabet. The witnessing three-state automaton is explicit: its reduced dynamics tracks the pair (u,u2), where u is the reversed base-b value of the input, and its acceptance functional is a downward parabola peaked at the value of the target string. Combined with Gill's classification of the binary strings with AP=2, this completely determines AP on binary strings.