Algebra Seminar talk
2023-02-14 (Tuesday! 11:15!)
Manfred Droste
Weighted automata over monotonic strong bimonoids: decidability and undecidability of finite image
Abstract:
A weighted finite automaton A has finite image
if the image of the weighted language associated with it is finite,
i.e., A generates only finitely many values.
First, we give a structural result characterizing when A has finite image. Then we characterize those past-finite monotonic strong bimonoids such that for each weighted finite automaton A it is decidable whether A has finite image. In particular, this is decidable over past-finite monotonic semirings.
Next, we give two undecidability results on the finite-image property of weighted finite automata over semirings, respectively strong bimonoids. We construct a computable idempotent commutative past-finite ordered semiring such that it is undecidable, for an arbitrary deterministic weighted finite automaton A over that semiring, whether A has finite image.
Finally, we construct a computable commutative past-finite monotonic ordered strong bimonoid such that it is undecidable, for an arbitrary weighted finite automaton A over that strong bimonoid, whether A has finite image.
This shows that the decidability results mentioned before cannot be extended to natural classes of ordered semirings and ordered strong bimonoids without further assumptions.
Joint work with Zoltan Fülöp, David Kószó, Heiko Vogler.