Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9952159 | Information Processing Letters | 2018 | 6 Pages |
Abstract
Two families of input-deterministic weighted automata over semirings are considered: purely sequential automata, in which terminal weights of states are either zero or unity, and sequential automata, in which states can have arbitrary terminal weights. The class of semirings over which all weighted automata admit purely sequential equivalents is fully characterised. A similar characterisation is proved for sequential automata under an assumption that all elements of the underlying semiring have finitely many multiplicative left inverses, which is in particular true for all commutative semirings and all division semirings.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Peter Kostolányi,