Determinizing and Unambiguizing Weighted Automata over the Rationals

Prelegent(ci)

Roland Guttenberg

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

21 października 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

Determinizing and Unambiguizing Weighted Automata over the Rationals

Seminarium

Seminarium „Teoria automatów”

In this talk I consider weighted automata (WA) over Q, and am interested in deciding whether there exists an equivalent (1) deterministic and (2) unambiguous WA. In the first half of the talk I state our first main result, an abstract theorem about quotients of semigroups, without proof. I then show how it implies a simple characterization of problems (1) and (2), and how this allows to decide (1) and (2) in PSPACE. 

In the second half of the talk I explain how to prove the quotient theorem by analyzing the subgroups of the given semigroup.

This is joint work together with Rida Ait El Manssour, Nathan Lhote, Mahsa Shirmohammadi and James Worrell.