2026-07-19T23:43:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10705 2024-03-06T10:46:30Z ddc:004 open_access

The Parametric Complexity of Lossy Counter Machines (Track B: Automata, Logic, Semantics, and Theory of Programming) Schmitz, Sylvain Counter machine well-structured system well-quasi-order antichain fast-growing complexity 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. We 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 < omega. We develop for this an approach through antichain factorisations of bad sequences and analysing the length of controlled antichains. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sylvain Schmitz 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.129 urn:nbn:de:0030-drops-107056 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.129 eng https://creativecommons.org/licenses/by/3.0/legalcode