Every string has probabilistic automatic complexity at most three
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$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.26275
curl -X POST /api/v1/records/arxiv/2607.26275/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.26275/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'