Probabilistic automatic complexity of finite strings

Kenneth Gill

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 explo…