Nie jesteś zalogowany | Zaloguj się

Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata

Prelegent(ci)
Filip Mazowiecki
Afiliacja
University of Warsaw
Termin
29 maja 2024 14:15
Pokój
p. 5050
Seminarium
Seminarium „Teoria automatów”

We study the determinisation and unambiguisation problems of weighted automata over the rational field: given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton?
Recent results by Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata.