文章基本信息

标题：The Parametric Complexity of Lossy Counter Machines
本地全文：下载
作者：Sylvain Schmitz
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-15
DOI：10.4230/LIPIcs.ICALP.2019.129
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Counter machine; well-structured system; well-quasi-order; antichain; fast-growing complexity