BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:7653@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20170124T110000
DTEND;TZID=Europe/Paris:20170124T120000
DTSTAMP:20241120T204748Z
URL:https://www.i2m.univ-amu.fr/evenements/synchronization-problems-in-aut
 omata-without-non-trivial-cycles/
SUMMARY:Andrew Ryzhikov (Laboratoire d'Informatique Gaspard-Monge\, Univers
 ité Paris-Est): Synchronization problems in automata without non-trivial 
 cycles
DESCRIPTION:Andrew Ryzhikov: The concept of synchronization in automata the
 ory 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 co
 ntrol can be returned (the subset synchronization problem) is known to be 
 a PSPACE-complete problem. I will speak about the restriction of this prob
 lem to the class of weakly acyclic automata\, which are the automata conta
 ining no cycles other than self-loops in their underlying digraph. Such au
 tomata form a proper subclass of well-studied aperiodic automata. In the c
 lass of weakly acyclic automata many synchronization problems remain surpr
 isingly hard. In particular\, the subset synchronization problem is NP-com
 plete\, and its generalization\, the problem of computing the rank of a su
 bset of states\, is hard to approximate within a polynomial factor. The re
 sults 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 prob
 lem of finding the chromatic number of a graph and provide some other prob
 lems that are hard in the class of weakly acyclic automata.\n\nhttps://arx
 iv.org/abs/1702.08144\n&nbsp\;
ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2
 020/01/Andrew_Ryzhikov.jpg
CATEGORIES:Séminaire,Ernest
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20161030T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR