Andrew Ryzhikov
Laboratoire d'Informatique Gaspard-Monge, Université Paris-Est
https://sites.google.com/site/ryzandrew/
Date(s) : 24/01/2017 iCal
11 h 00 min - 12 h 00 min
The concept of synchronization in automata theory is a formalization of the idea of returning control over an automaton in a situation where its current state in unknown. If the current state is known to be in some particular subset of states, checking whether the control can be returned (the subset synchronization problem) is known to be a PSPACE-complete problem. I will speak about the restriction of this problem to the class of weakly acyclic automata, which are the automata containing no cycles other than self-loops in their underlying digraph. Such automata form a proper subclass of well-studied aperiodic automata. In the class of weakly acyclic automata many synchronization problems remain surprisingly hard. In particular, the subset synchronization problem is NP-complete, and its generalization, the problem of computing the rank of a subset of states, is hard to approximate within a polynomial factor. The results remain true even in the case where the alphabet of the automaton is binary. I will show the connection of the mentioned problems with the problem of finding the chromatic number of a graph and provide some other problems that are hard in the class of weakly acyclic automata.
https://arxiv.org/abs/1702.08144
Catégories