Probabilistic automatic complexity of finite strings

We introduce a new complexity measure for finite strings using probabilistic finite-state automata (PFAs), in the same spirit as existing notions employing DFAs and NFAs, and explore its properties. The PFA complexity AP(x) is the least number of states of a PFA for which x is the most likely string of its length to be accepted. The variant AP,δ(x) adds a real-valued parameter δ specifying a lower bound on the gap in acceptance probabilities between x and other strings. We relate AP to the DFA and NFA complexities, obtain a complete classification of binary strings with AP=2, and prove AP,δ(x) is computable for every x and for cofinitely many δ (depending on x). Finally, we discuss several other variations on AP with a view to obtaining additional desirable properties.