Nie jesteś zalogowany |
Minimising ambiguity of weighted automata
- Prelegent(ci)
- Antoni Puch
- Afiliacja
- University of Warsaw
- Język referatu
- angielski
- Termin
- 23 października 2024 14:15
- Pokój
- p. 5440
- Tytuł w języku polskim
- Minimising ambiguity of weighted automata
- Seminarium
- Seminarium „Teoria automatów”
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.
