Invited Speakers
Stacks Image 66
Patricia Bouyer-Decitre (LSV, CNRS & ENS de Cachan, France)

On the optimal reachability problem in weighted timed automata and games
Stacks Image 69
Sylvain Lombardy (LaBRI, Bordeaux, France)

"On two-way weighted automata"

Two-way automata are a natural extension to automata. Without weights, it occurs that they are not more powerful than one-way automata. We show that the definition of two-way weighted automata requires to be cautious, and that they are more powerful than one-way automata in various ways. First, they can realize non rational series, but they can also deterministicly realize some rational computations that can not be realized by deterministic one-way weighted automata.
Stacks Image 72
Emanuele Rodaro (CMUP, University of Porto, Portugal)

“New reformulations of Cerny's conjecture and related problems”

Cerny's conjecture is one of the most longstanding open problems in the theory of finite automata (stated by Cerny in 1964). It deals with synchronizing automata, i.e. finite deterministic semiautomata possessing a word whose action sends all the states in a single state. This conjecture claims that a synchronizing deterministic finite semiautomaton with $n$ states has always a synchronizing word of length \((n-1)^{2}\). Although many attempts have been done to tackle this conjecture, not even an upper bound of magnitude \(O(n^2)\) for the length of the shortest synchronizing word has been known so far. The best known upper bound is \(\frac{n^3-n}{6}\) found by Pin in 1983. In this talk, I am going to show two different approaches of Cerny's conjecture and the problem of finding quadratic bounds; one using an algebraic perspective and the other one using a language theoretic strategy. The algebraic strategy is based on the Wedderburn-Artin theory, while the language theoretic approach stems from the representability of two-sided ideals by means of certain decompositions in left ideals. From these two points of view, new reformulations of Cerny’s conjecture and other weaker conjectures arise. In particular, we show that the solution of a weaker version of Cerny’s conjecture for a subclass of semisimple semiautomata would give a general quadratic bound of magnitude \(2(n-1)^2\) for the shortest synchronizing word.