{"id":"arxiv/2607.26275","url":"https://arxiv.org/abs/2607.26275","tags":["cs.FL","math.LO"],"score":0,"title":"Every string has probabilistic automatic complexity at most three","domain":"cs.FL","source":"arxiv","authors":["Bjørn Kjos-Hanssen"],"reviews":0,"subject":"cs.FL","summary":"Gill (arXiv:2402.13376) introduced the probabilistic automatic complexity $A_P(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 $A_P$ is unbounded, noting that no string with $A_P > 3$ was known (Question 4.14 of that paper). We answer the question by proving that $A_P(w)\\le 3$ for every string $w$ over every finite alphabet. The witnessing three-state automaton is explicit: its reduced dynamics tracks the pair $(u,u^2)$, where $u$ is the reversed base-$b$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-28","reactions":{}}