BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260526T091423Z
UID:Seminar-verification-698@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Patrick Totzke:MAILTO:totzke@liverpool.ac.uk
DTSTART:20200609T110000
DTEND:20200609T120000
SUMMARY:Verification Series
DESCRIPTION:Patrick Totzke: Parametrized Universality Problems for One-Counter Nets\n\nWe study the language universality problem for One-Counter Nets, also known as 1-dimensional Vector Addition Systems with States (1-VASS), parameterized either with an initial counter value, or with an upper bound on the allowed counter value during runs. The language accepted by an OCN (defined by reaching a final control state) is monotone in both parameters. This yields two natural questions:\n1. does there exist an initial counter value that makes the language universal?\n2. does there exist a sufficiently high ceiling so that the bounded language is universal?\n\nDespite the fact that unparameterized universality is Ackermann-complete and that these problems seem to reduce to checking basic structural properties of the underlying automaton, we show that in fact both problems are undecidable.\n\nWe also look into the complexities of the problems for several decidable subclasses, namely for unambiguous, and deterministic systems, and for those over a single-letter alphabet.\n\nThis is unpublished joint work with Shaull Almagor, Udi Boker, and Piotr Hofman.\nI will (attempt to) give a "blackboard" talk instead of showing fancy slides.\nA draft version can be found on the arXiv: http://arxiv.org/abs/2005.03435\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=698
LOCATION:
END:VEVENT
END:VCALENDAR