Quantitative synchronizing automata

Room M005, DMat-FCUP
Friday, 5 July, 2013 - 13:30

Synchronizing automata has previously been studied for finite automata. In a finite automaton, a word is synchronizing if reading that word from any state of the automaton always leads to the same state. Synchronizing words have applications in security, biocomputing, planning, control of discrete event systems and robotics. In particular, we are interested in the latter ones: a synchronizing word is useful in case the controller looses control over a system and want to restore the control. For this setting, a finite state automata is not a rich framework since some realistic aspects are missing. As an example consider a system that needs to be synchronized in less than a certain time or an uncertain system that responses randomly to the action done by the controller.
We have studied (quantitative) synchronizing words in richer models like timed automata, weighted automata and probabilistic automata. In this talk, I first present the definition of synchronizations in such automata. Next, we show that this semantics generalizes the classical notion of synchronizing words for finite automata. We consider the membership problem, which asks whether some quantitative word is synchronizing by a given automaton. We see some reductions to show lower bounds and undecidability results of membership problem for a class of definitions in probabilistic automata and weighted automata.

Speaker: 

Mahsa Shirmohammadi (LSV, ENS de Cachan, France and ULB, Belgium)