Determinizing and Unambiguizing Weighted Automata over the Rationals

Speaker(s)

Roland Guttenberg

Affiliation

University of Warsaw

Language of the talk

English

Date

Oct. 21, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Determinizing and Unambiguizing Weighted Automata over the Rationals

Seminar

Seminar Automata Theory

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.