moteur de recherche

Séminaire Algo - Andrew Ryzhikov
Séminaire Algo - Andrew Ryzhikov
19-déc.-2017 14:30
Il y a: 214 days

Andrew Ryzhikov

Some generalizations of synchronization in partial and complete DFAs

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: A deterministic finite automaton (DFA) is called synchronizing if there exists a word (called a synchronizing word) sending all its states to some particular state. This concept is an abstraction of returning control over a system with known structure and unknown current state: the application of a synchronizing word transits the automaton into a known state. Synchronizing automata are a source of interesting combinatorial problems, such as the (solved) road coloring problem and the (unsolved) Černý conjecture.

I will talk about different variations of synchronization for DFA. What happens, if we have some partial infornation about the current state (subset synchronization)? Or if the DFA is not complete (careful synchronization)? Or if the DFA is not synchronizing? All these question turn to be related to each other and to some other problems such as intersection of languages of several DFAs. The accent will be on extremal and computational complexity questions for these concepts.

<- retour: