The Parametric Complexity of Lossy Counter Machines

Speaker(s)

Sylvain Schmitz

Affiliation

CNRS & ENS Paris-Saclay

Date

May 29, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

   The reachability problem in lossy counter machines is the best-known
   ACKERMANN-complete problem and has been used to establish most of the
   ACKERMANN-hardness statements in the literature.  This hides however a
   complexity gap when the number of counters is fixed.

   I'll show how to close this gap and prove F_d-completeness for
   machines with d counters, which provides the first known uncontrived
   problems complete for the fast-growing complexity classes at levels
   3 < d < ω.  This is shown through antichain factorisations of bad
   sequences and analysing the length of controlled antichains.

   This work will be presented at ICALP'19 and a preprint is available
   from https://hal.archives-ouvertes.fr/hal-02020728 .

---