BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T164117Z
UID:Seminar-ACTO-500@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20191120T140000
DTEND:20191120T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Dr Andrew Ryzhikov: Synchronization of finite automata\n\nImagine a reactive system modeled by a complete DFA. We know the structure of this DFA and we can observe its input, but we don't know its current state. Our goal is to eventually discover in which state the DFA is. This is possible if and only if there exists a word (called a reset word) which sends all the states to one particular state. Automata which admit reset words are called synchronizing, and the minimum length of reset words is the subject of the ?ernư conjecture, one of the oldest open problems in automata theory. I will explain the extensions of this concept to the more general classes of partial DFAs and unambiguous NFAs, describe some extremal and algorithmic results for the mentioned classes, and show their tight connection with variable length codes.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=500
LOCATION:
END:VEVENT
END:VCALENDAR