The Parametric Complexity of Lossy Counter Machines

Prelegent(ci)

Sylvain Schmitz

Afiliacja

CNRS & ENS Paris-Saclay

Termin

29 maja 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

   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 .

---