Frequency Computable Relations
Madara Augstkalne · 2012
A transducer is a finite-state automaton with an input and an output. We compare possibilities of nondeterministic and probabilis- tic transducers, and prove several theorems which establish an infinite hierarchy of relations computed by these transducers. We consider only left-total relations (where for each input value there is exactly one al- lowed output value) and Las Vegas probabilistic transducers (for which the probability of any false answer is 0). It may seem that such limita- tions allow determinization of these transducers. Nonetheless, quite the opposite is proved; we show a relation which can only be computed by probabilistic (but not deterministic) transducers, and one that can only be computed by nondeterministic (but not probabilistic) transducers. Frequency computation was introduced by Rose and McNaughton in early sixties and developed by Trakhtenbrot, Kinber, Degtev, Wechsung, Hinrichs and others. It turns out that for transducers there is an infi- nite hierarchy of relations computable by frequency transducers and this hierarchy differs very much from similar hierarchies for frequency com- putation by a) Turing machines, b) polynomial time Turing machines, c) finite state acceptors.