The Technion Theory Lunch is a seminar run by the theory group at the Department of Computer Science, Technion. The seminar holds weekly meetings in which graduate students and faculty from the Technion and other universities in Israel and abroad present recent results or other interesting topics in theoretical computer science. The seminar is open to faculty, graduate and undergraduate students interested in theory of computing.
Wednesdays, 13:00-14:00 (food starts at 12:45)
Room 401, Taub Building
If you are interested in giving a talk at the seminar, contact Omri Ben-Eliezer and/or David Wajc.
The seminar’s mailing list is used to announce our weekly meetings, and also to publicize CS theory related events, such as workshops and seminars, in Israel and abroad.
To join or leave our mailing list.
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.
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.
Omrit Filtser (Open University)
Upcoming
