Probabilistic automatic complexity of finite strings
<|reference_start|>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 $A_P(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 $A_{P,\delta}(x)$ adds a real-valued parameter $\delta$ specifying a required lower bound on the gap in acceptance probabilities between $x$ and other strings. We prove $A_{P,\delta}$ is $\delta$-computable for all $\delta$, relate $A_P$ to the DFA and NFA complexities, and obtain a complete classification of binary strings with $A_P=2$. Finally, we discuss several other variations on $A_P$ with a view to obtaining additional desirable properties.<|reference_end|>
@article{gill2024probabilistic,
    title={Probabilistic automatic complexity of finite strings},
    author={Kenneth Gill},
    journal={arXiv preprint arXiv:2402.13376},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.13376},
    primaryClass={cs.FL math.LO}
}