Weighted Automata over Fields - Determinization and related problems

A weighted finite automaton (WFA) computes a function that maps each input word to an output in an underlying semiring of weights. Two WFA are equivalent if they compute the same function. While every boolean (i. e. , unweighted) finite automaton is equivalent to a deterministic one, this is no longer true for weighted automata. In general, there are strict inclusions between the classes of functions computable by deterministic (=sequential), unambiguous, finitely ambiguous, polynomial ambiguous, and exponentially ambiguous WFA, giving rise to a natural ambiguity hierarchy. While it is classically known to be decidable whether a given automaton is deterministic, unambiguous, etc. , it is much harder to decide whether a WFA is equivalent to a deterministic, unambiguous, etc. WFA. In particular, deciding determinizability for WFA is a classical problem, typically considered over tropical (min/max-plus) semirings or over fields. The tropical case is still not fully resolved. This talk is about the field case. I will discuss joint work with Jason Bell (Waterloo), which shows that equivalence with deterministic, respectively, unambiguous WFA is decidable. The approach is based on a characterization of the semantics, i. e. , the functions computed by such WFA, using arithmetic properties and a theorem from Diophantine number theory. I will also discuss current work together with Antoni Puch (Warsaw). Restricting to the case in which all transition matrices are invertible, we obtain a complete correspondence between the ambiguity hierarchy and arithmetical properties. This shows that also equivalence with finitely ambiguous and polynomial ambiguous WFA is decidable in the invertible case.

Authors

• Daniel Smertnig

Keywords

No keywords are indexed for this paper.