Realizations by stochastic finite automata

✍ Scribed by J.W. Carlyle; A. Paz

• Publisher: Elsevier Science
• Year: 1971
• Tongue: English
• Weight: 729 KB
• Volume: 5
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(71)80005-3

✦ Synopsis

It is shown that a real-valued functionf(x), defined for strings x over a finite alphabet, is of the form (fig(x) + y) exp (3[ x ]) for constants fi, y, 3, and the acceptance probability function g for a probabilistic automaton, if and only iff is of finite rank, where the latter external criterion is equivalent to the internal realizability off by a finite-state sequential system permitted to have arbitrary real initial, transition, and output weights. The development encompasses multiple numerical outputs (finite vectors of functions of strings) and the corresponding generalization of this theorem; as an intermediate step, a set of sufficient conditions is established for equivalence of sequential systems (ss) with multiple outputs, yielding procedures for conversion of ss to numericaloutput probabilistic automata (npa). Additional instances are given of application of these ideas in constructing npa equivalent to certain ss.