CS Paper Radar

Symmetric two-counter machines

Krzysztof Jaros, Łukasz Kamiński, Maja Kądziołka, Sławomir Lasota

cs.FL ·submitted 2026-10-16 14:06 UTC · v2
theory

Abstract

Counter machines are a particularly simple, Turing-complete model of computation. We study the expressive power of nondeterministic 2-counter machines which are symmetric, in that their set of update transitions is invariant under swapping of counters. Our model is an extension of symmetric 2-VASS, in that we allow modifying both counters within a single transition. As the main result we demonstrate a dramatic impact of symmetry: we show that symmetric 2-counter machines are not Turing-complete, by proving decidability of their reachability problem. We conjecture that the decidability extends to machines with 3 or more counters that are symmetric, meaning the set of update transitions is invariant under any permutation of counters. We leave this problem open for machines with 3 and more counters, while identifying a frontier of the impact of symmetry: we prove undecidability for 3-counter machines invariant under the cyclic permutation group of order 3.

Closest papers

Nearest neighbours by meaning across the whole index.

Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable

cs.FL cs.LO ·2026-10-29 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.67
Abstract · 31 pages, 3 figures. Rocq artifact: https://doi.org/10.5281/zenodo.23734555

Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, $Π^0_1$-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet $Σ_2=\{e:0,d:2\}$, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over $Σ_2$. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled $\bot$.

0.32

Undecidability of Confluence for Binary Length-Reducing Cycle Rewriting

cs.LO cs.FL ·2026-08-19 ·Graham Campbell
similarity 0.61
Abstract

Confluence guarantees that diverging rewrite choices can always be rejoined. For finite terminating string- and term-rewriting systems, confluence is decidable by critical-pair analysis, and in polynomial time for length-reducing strings. For finite terminating (hyper)graph transformation systems, in contrast, confluence is undecidable. We show that undecidability already appears for words on a circle, that is, strings up to rotation. Confluence of finite cycle-rewriting systems over the fixed alphabet $\{0,1\}$ is undecidable, indeed $Π^0_1$-complete, even when every rule has a nonempty right-hand side and strictly reduces length. Under this restriction termination is syntactically evident, and derivations from a nonempty length-$n$ cycle have fewer than $n$ steps. The same holds over every fixed alphabet with at least two letters, while the one-letter case is decidable. Rotation alone separates cyclic from string rewriting. The proof compiles a deterministic verifier into a weighted cycle system with one controlled branch, then into a binary length-reducing system via a run-length code whose cleanup rules send every reducible malformed cycle to one error normal form.

0.29

Bridging the Gap Between Plain VASS and Branching VASS

cs.LO cs.FL ·2026-09-14 ·Clotilde Bizière, Jérôme Leroux, Grégoire Sutre
publishedtheory similarity 0.61
Abstract · 25 pages, extended version of the paper with same title and same authors presented at FOSSACS'26

Vectors addition systems with states (VASS), a model equivalent to Petri nets, are finite-state machines with finitely many counters ranging over the natural numbers. The decidable reachability problem for VASS has many applications in logic, automata, and verification. In this paper we study the reachability problem for BVASS, a branching generalization of VASS. We show that BVASS reachability sets are very similar to VASS reachability sets, namely that they are sections of VASS. Our proof relies on a new well-quasi-order (wqo) on BVASS runs that generalizes the well-known wqo on VASS runs. By leveraging an amalgamation property, we prove that every BVASS run can be transformed into an equivalent one of bounded branching complexity. This allows us to derive several results on the geometry of BVASS reachability sets. As an application we obtain that reachability sets of 5-dimensional BVAS are effectively semilinear, as is the case for 5-dimensional VAS.

0.58

Safety Analysis of Parameterized Networks with Shared Counters

cs.LO ·2026-11-13 ·June Roupin, Arnaud Sangnier
similarity 0.60
Abstract

We study networks with an unbounded number of processes sharing some natural counters that can be decremented, incremented and tested to zero. We look at two safety problems: the first one asks whether there is a network with an execution bringing a process in a given final state and the other one asks the execution to bring all the processes in the final state. In their full generality, these two problems are undecidable, but we show that decidability can be regained by either using a single counter or by forbidding the use of zero-tests (as it is is the case in Vector Addition Systems with States). For these decidable cases, we obtain low complexity results, the problems being solvable either in non-deterministic logarithmic space or in polynomial time.

0.26

Parameterized Reachability for Register Machines with Data

cs.FL ·2026-10-06 ·Parosh Aziz Abdulla, Mohammed Faouzi Atig, Abhijith R Nair, K Narayan Kumar, Prakash Saivasan
similarity 0.60
Abstract

We investigate the parameterized reachability problem for concurrent register machines over infinite data domains. In this framework, each machine is a program equipped with a set of local registers, the communication across machines is mediated through a set of shared registers. Both local and shared registers can take values from an infinite data domain. The program's primitive operations include copying values between registers, assigning constants, comparing registers for (dis-)equality, and nondeterministic assignments that store an arbitrary domain value into a local register. The parameterized reachability problem considers a program and a target location, asking whether there exists some n in Naturals such that an execution of n identical machines (referred to as instances) results in at least one instance reaching the specified location. We show that this problem is Pspace-complete in the general case and it becomes undecidable if a freshness assumption (i.e., each assignment must produce a unique value distinct from all constants) is applied to nondeterministic assignments. This undecidability persists even for systems restricted to two shared and two local registers. Finally, we establish optimal decidability results for two restricted settings: when each thread is limited to a single local register, or when the system utilizes only one shared register.

0.30

The existence of polyhedral invariants is undecidable for linear systems

cs.LO ·2026-09-25 ·David Monniaux
similarity 0.60
Abstract

The existence of polyhedral inductive invariants suitable for proving that a given control location is unreachable is undecidable for programs using only linear arithmetic over Z or Q, by reduction from 2-counter machines.

0.30

On Small Universal Reversible Turing Machines

cs.FL cs.LO ·2026-10-30 ·T. Yokoyama
code/data similarity 0.59
Abstract · The constructions and the nonexistence results are formalized in Lean 4 with Mathlib; the formalization and the rule tables are available at…

A reversible Turing machine (RTM) is a Turing machine in which every instantaneous description has at most one predecessor. Writing URTM(m,n) for a universal RTM with m states and n symbols, we construct URTM(3,600), URTM(4,41), URTM(5,37), URTM(6,30), URTM(7,28), URTM(8,21), and URTM(85,2); each of them has fewer states or fewer symbols than each of the nine URTMs in Morita's book (2017). They come from improved versions of Morita's conversions to three states, to four states, and to two symbols; for example, the improved conversion to three states uses O(mn^2) symbols instead of O(m^2n^3). We also show that the halting problem of RTMs with at most two states is decidable for finite instantaneous descriptions, so that no RTM with at most two states is universal under any notion of universality that reduces the halting problem of Turing machines to it by a computable encoding into finite instantaneous descriptions; in particular, there is no URTM with at most two states in our formalization of Morita's definition. We also show that no three-state, two-symbol RTM is universal in that formalization.

0.40

Reachability in Five-Dimensional Vector Addition Systems Is PSPACE-Complete

cs.FL cs.CC ·2026-10-29 ·Weijun Chen, Bo Fu, Yuxi Fu
theory similarity 0.59
Abstract · 69 pages,1 figure

Vector addition systems (VAS) are a fundamental model of concurrent computation in which transitions update nonnegative integer counters by adding integer vectors, provided all counters remain nonnegative. Closely related to Petri nets, VAS are the single-state counterpart of vector addition systems with states (VASS), which use finitely many states to restrict the available transitions. A classical simulation of $d$-VASS by $(d+3)$-VAS connects their reachability problems, but the complexity-theoretic picture of fixed-dimensional VAS remains largely unclear. While reachability in $2$-VASS is PSPACE-complete under binary encoding, the best known upper bound for $5$-VAS was only elementary. We prove that every reachable $5$-VAS instance has a reachability witness of length polynomial in its unary size. Consequently, $5$-VAS reachability is NL-complete under unary encoding and PSPACE-complete under binary encoding. We also establish a polynomial factorization of the reachability relation of every $d$-VAS with $d \ge 3$. For $5$-VAS, this strengthens Hopcroft and Pansiot's effective semilinearity of reachability sets to the full reachability relation. For every fixed $d\ge3$, it also yields an $\mathsf F_d$ upper bound for reachability in $(d+3)$-VAS.

0.16