The Complexity of Nested Reset Counter Systems

A. R. Balasubramanian, Franzisco Schmidt · 2026

Read The Complexity of Nested Reset Counter Systems by A. R. Balasubramanian, Franzisco Schmidt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14850.txt.

Description

A. R. Balasubramanian and Franzisco Schmidt extend nested counter systems, which stack counters inside counters like trees, with reset operations. Coverability asks whether a target tree can be reached from a start tree. The pair proves coverability for order-k reset systems is complete for the fast-growing class F of omega-tower height k. That gives a first natural ladder of complete problems for these classes, and it tightens bounds for XML, graph rewriting, and parameterized verification problems.

Catalog record

CREATORA. R. Balasubramanian, Franzisco Schmidt
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE283267
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14850

Browse the full library · About the Tower of Babel