BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T013750Z
UID:Seminar-dept-417@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20160913T130000
DTEND:20160913T140000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Friedrich Otto: On Nondeterministic Ordered Restarting Automata\n\nWhile (stateless) deterministic ordered restarting automata accept exactly the regular languages,\n\nit is known that nondeterministic ordered restarting automata accept some languages that\n\nare not even growing context-sensitive. In fact, the class of languages accepted by these automata\n\nis an abstract family of languages that is incomparable to the (deterministic) linear languages,\n\nthe (deterministic) context-free languages, and the growing context-sensitive languages with respect to inclusion, and the emptiness problem is decidable for these automata. These results are derived by using a Cut-and-Paste Lemma for nondeterministic ordered restarting automata that is based on Higman's theorem. Here we extend the arguments used in that proof to actually derive a real Pumping Lemma for these automata. Based on this Pumping Lemma, it can be shown that the finiteness problem is also decidable for these automata, and that the only unary languages these automata accept are the regular ones. In addition, we present a new and simplified proof for the fact that stateless ordered restarting automata  only accept regular languages.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=417
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR