Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

The Taub Faculty of Computer Science Events and Talks

Determinization of Min-Plus Weighted Automata
event speaker icon
Guy Arbel (M.Sc. Thesis Seminar)
event date icon
Wednesday, 28.05.2025, 13:00
event location icon
Taub 601 & Zoom
event speaker icon
Advisor: Dr. Shaull Almagor & Dr. Sarai Sheinvald

Min-Plus Weighted Finite Automata (WFAs) are a quantitative extension of Boolean automata whereby each word is assigned an integer, instead of being accepted or rejected.

Applications of WFAs fall on a wide spectrum including verification, rewriting systems, tropical algebra, speech and image processing and have been key to proving the star-height conjecture. 
Unlike Boolean automata, WFAs cannot always be determinized. The decidability of whether a WFA admits an equivalent deterministic WFA is a long standing open problem.

We prove that this problem is decidable.
As part of the proof, we develop a new toolbox for reasoning about the run structure of weighted automata.