Overview
Research establishes an upper bound for the probabilistic automatic complexity $A_P(w)$ of any finite string $w$, demonstrating that $A_P(w) \le 3$. This finding addresses a question posed by Gill (arXiv:2402.13376) regarding whether $A_P$ is unbounded and the absence of strings with an $A_P \le 3$ in prior knowledge. The work provides an explicit three-state automaton that supports this bound for all strings over any finite alphabet.
Research Context
The concept of probabilistic automatic complexity, $A_P(w)$, was introduced by Gill (arXiv:2402.13376). It is defined as the minimum number of states in a probabilistic finite automaton (PFA) for which a given finite string $w$ is the unique most probably accepted string of its specific length. Gill's initial work included a question (Question 4.14) regarding the boundedness of $A_P$ and noted that no string with an $A_P \le 3$ had been identified at that time.
Approach
The research addresses Gill's question by working to determine the upper bound of $A_P(w)$ for any string $w$. The methodology involved the construction and description of an explicit three-state automaton. This automaton is designed to serve as a witness, indicating that a PFA with three states can satisfy the conditions for any string $w$ to be its unique most probably accepted string of its length, thereby establishing $A_P(w) \le 3$.
Findings
- The probabilistic automatic complexity $A_P(w)$ for every string $w$ over every finite alphabet is found to be at most three ($A_P(w)\le 3$).
- An explicit three-state automaton serves as a witness for this bound.
- The reduced dynamics of this explicit three-state automaton tracks the pair $(u,u^2)$, where $u$ represents the reversed base-$b$ value of the input.
- The acceptance functional of this three-state automaton is a downward parabola, which is specifically peaked at the value of the target string.
- When combined with Gill's prior classification of binary strings for which $A_P=2$, this result entirely determines the probabilistic automatic complexity $A_P$ for all binary strings.
Why This Matters
This research provides a definitive answer to a foundational question regarding the probabilistic automatic complexity of finite strings. By establishing a tight upper bound and providing an explicit automaton, it clarifies a fundamental property within the computational complexity of strings accepted by probabilistic finite automata. The complete determination of $A_P$ for binary strings represents a specific and conclusive advancement in this subfield.