出版社：Vilnius University, University of Latvia, Latvia University of Agriculture, Institute of Mathematics and Informatics of University of Latvia
摘要：A transducer is a finite-state automaton with an input and an output. We compare possibilities of nondeterministic and probabilistic 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 allowed output value) and Las Vegas probabilistic transducers (for which the probability of any false answer is 0). It may seem that such limitations 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 infinite hierarchy of relations computable by frequency transducers and this hierarchy differs very much from similar hierarchies for frequency computation by a) Turing machines, b) polynomial time Turing machines, c) finite state acceptors.
