×

The implicating vector problem and its applications to probabilistic and linear automata. (English) Zbl 0658.15024

Fundamentals of computation theory, Proc. Int. Conf., Kazan/USSR 1987, Lect. Notes Comput. Sci. 278, 132-136 (1987).
[For the entire collection see Zbl 0633.00025.]
It is important in many problems to be able to present one or several stochastic matrices in the form of convex combination (CC) of deterministic stochastic matrices. At the same time it is desirable to have CC of minimal length, namely, with minimal number of nonzero coefficients and the same collection of these coefficients which is called minimal implicating vector (MIV). A particular case is the synthesis problem for finite probabilistic automata (PA) in the form of junction of random-symbol generator with a deterministic automata system. Another problem consists in extending the approach in PA theory to the case of linear automata (LA). This paper presents some results on the MIV problem in the context of the PA and LA theories, its generalizations and applications.
Reviewer: M.de la Sen

MSC:

15B51 Stochastic matrices
68Q70 Algebraic theory of languages and automata
06E10 Chain conditions, complete algebras

Citations:

Zbl 0633.00025