BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260502T024937Z
UID:Seminar-verification-697@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Patrick Totzke:MAILTO:totzke@liverpool.ac.uk
DTSTART:20200512T110000
DTEND:20200512T120000
SUMMARY:Verification Series
DESCRIPTION:Karoliina Lehtinen: Good-for-games omega-pushdown automata\n\nGood-for-gameness is the new determinism, and not just for solving games.\nGood-for-games automata, originally due to Henzinger and Piterman, are nondeterministic automata that have many of the desirable properties of deterministic automata and can therefore often be used in their stead to circumvent determinisation. In the context of regular languages of infinite words they can be exponentially more concise than any equivalent deterministic automaton.\n\nIn this talk I will first give an overview of good-for-games automata and then discuss what happens when good-for-gameness is lifted into the context-free setting. In brief, it turns our that good-for-games pushdown automata are more expressive and not just more concise than their deterministic counterparts. This gives us a novel class of languages for which solving games and universality -- which are both undecidable for pushdown automata -- are decidable in EXPTIME.\n\nThis talk is based on joint work with Martin Zimmermann, accepted for publication at LICS'2020.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=697
LOCATION:
END:VEVENT
END:VCALENDAR