On Stochastic Automata over Monoids
This work addresses foundational issues in automata theory for researchers in theoretical computer science, but it appears incremental as it builds on prior results like Turakainen's.
The paper tackles the problem of defining stochastic automata over monoids by introducing an extension postulate to ensure well-definedness, and shows that these generalized automata have the same acceptance power as their stochastic counterparts, generalizing Turakainen's result.
Stochastic automata over monoids as input sets are studied. The well-definedness of these automata requires an extension postulate that replaces the inherent universal property of free monoids. As a generalization of Turakainen's result, it will be shown that the generalized automata over monoids have the same acceptance power as their stochastic counterparts. The key to homomorphisms is a commuting property between the monoid homomorphism of input states and the monoid homomorphism of transition matrices. Closure properties of the languages accepted by stochastic automata over monoids are investigated. matrices. Closure properties of the languages accepted by stochastic automata over monoids are investigated.