BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T205220Z
UID:Seminar-verification-1292@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Patrick Totzke:MAILTO:totzke@liverpool.ac.uk
DTSTART:20251016T110000
DTEND:20251016T120000
SUMMARY:Verification Series
DESCRIPTION:Soumyajit Paul: Resolving Nondeterminism by Chance \n\nHistory-deterministic automata are those in which nondeterministic choices can\n\nbe correctly resolved stepwise: there is a strategy to select a continuation of\n\na run given the next input letter so that if the overall input word admits some\n\naccepting run, then the constructed run is also accepting. The notion of\n\nHistory Determinism (sometimes known as Good for Games) was introduced by\n\nHenzinger and Peterman in 2006 motivated by applications in reactive synthesis.\n\nLater, it has been studied for several models such as Pushdown systems, Timed\n\nautomata, Vector Addition systems, etc. Motivated by checking qualitative\n\nproperties in probabilistic verification, we study the setting where the\n\nresolver strategy can randomize and only needs to succeed with lower-bounded\n\nprobability. In this talk, I will present our work on stochastic resolution of\n\nnondeterministic automata.\n\n\n\nI will discuss the expressiveness of stochastically-resolvable automata as well\n\nas our complexity results for deciding stochastic resolvability. In particular,\n\nwe show that it is undecidable to check if a given NFA is stochastically\n\nresolvable with a given threshold. The problem however becomes decidable for\n\nthe class of finitely-ambiguous automata. We also consider the related question\n\nof deciding whether an automata is resolvable with any positive threshold. We\n\nshow that this problem is decidable for automata over unary alphabet as well as\n\nfor finitely-ambiguous automata. I will present our complexity results for\n\nseveral well-studied classes of automata and also discuss natural extensions of\n\nsome of these results to automata for omega regular languages. I will conclude\n\nwith some interesting open questions.\n\n\n\nThis is based on joint work with David Purser, Sven Schewe, Qiyi Tang, Patrick\n\nTotzke and Di-de Yen\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1292
LOCATION:Ashton 208
END:VEVENT
END:VCALENDAR