Minimising ambiguity of weighted automata

Speaker(s)

Antoni Puch

Affiliation

University of Warsaw

Language of the talk

English

Date

Oct. 23, 2024, 2:15 p.m.

Room

room 5440

Title in Polish

Minimising ambiguity of weighted automata

Seminar

Seminar Automata Theory

---

By bounding the number of accepting runs of automata we obtain various subclasses of them. We consider: unambiguous automata, finitely-ambiguous automata, and polynomially-ambiguous automata, where the number of runs is bounded by 1, a constant, a polynomial in the size of the input word, respectively. We study these classes for weighted automata over fields.

Checking whether an input automaton is in one of the classes is easy and well-understood, it amounts to detecting simple graph patterns. We consider a more difficult problem whether the input automaton is equivalent to another automaton in one of the classes. In 2021 Bell and Smertnig proved Reutenauer's conjecture: characterising automata equivalent to unambiguous automata by arithmetic properties of the set of output values. This leads to an algorithm deciding whether an input automaton is equivalent to an unambiguous one. In this talk we will discuss our follow-up results providing similar characterisations for finitely-ambiguous and polynomially-ambiguous classes, with the additional assumption that the transition matrices are invertible. Based on joint work with Daniel Smertnig.

---