WorksComputer Science
Symmetric two-counter machines
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.
Funding Krzysztof Jaros: Supported by the NCN grant 2024/55/B/ST6/01674. Łukasz Kamiński: Supported by the NCN grant 2024/55/B/ST6/01674. Maja Kądziołka: Supported by the NCN grant 2024/55/B/ST6/01674. Sławomir Lasota: Partially supported by ERC grant INFSYS, agreement no. 950398, and by the NCN grant 2024/55/B/ST6/01674.
Acknowledgements We thank Roland Guttenberg and Vaios Michalakis for insightful discussions on the topic of this research, as well as Samira Bertsch and Violet Promeuschel for their helpful remarks which helped shape the exposition in this paper.
Disclosure. Large language models have been used to assist with proofreading and checking the correctness of the text. The authors remain fully responsible for the content of the paper, and are confident that its quality was not negatively impacted by the inherent shortcomings of the technology.
Introduction
Counter machines (CMs) are a particularly simple model of computation [23]. A counter machine has a number of registers, called counters, each register storing a natural number. Although the instruction set may vary, a common one consists of: counter increment, counter decrement, and counter zero-test. Many variants of the model have been introduced and studied, and both deterministic and nondeterministic machines are widely studied in the literature (often under different names, for instance counter automata). Numerous syntactic restrictions of the model are also widely studied [12, 14, 13, 10] since, as shown already by Minsky in the early 1960s [22], in its full generality the model is Turing-complete: deterministic 2-counter machines can faithfully simulate Turing machines and have an undecidable halting problem.
The purpose of this paper is to understand the impact of symmetry on the expressive power of CMs. We investigate the nondeterministic model, where a machine may choose between different instructions executable in the same state.
Symmetric counter machines. Imposing a symmetry condition on the transitions of a counter machine is inherently sensitive to what can be expressed within a single instruction. As such, we specifically choose the set of machine instructions: counter updates that simultaneously modify all counters by corresponding deltas, and counter zero-tests, which are executable only if a given counter has value zero. Every transition of a machine changes its state from to , and executes an attached instruction . Executing a transition in a given configuration constitutes a step of a machine. The model we investigate is thus essentially VASS (vector addition systems with states) [13] extended with zero-tests, and is clearly equivalent to standard CMs. In this paper we mostly focus on CMs that are symmetric, by which we mean that the set of update transitions is invariant under all permutations of counters: for every update transition , the machine has also a transition , where acts on an update instruction by permuting the roles of the counters (see Figure 1 for an example). To stress this point, we choose to impose the invariance only on update transitions, but not on zero-test transitions — imposing the invariance (symmetry) also on zero-tests is not needed for our main decidability proof.

Figure 1. An example symmetric 2-counter machine with two control states and six transitions, including five symmetric update transitions (invariant under the swap of counters) and one zero-test transition. Due to the symmetry condition, e.g. the transition also forces to exist. In contrast, we permit zero-test without a corresponding zero-test transition. Also notice the update transition, which is self-symmetric.
Contribution. The initial motivation of this study is the immense impact of symmetry on the complexity of the VASS reachability problem: while the problem is ACKERMANN-complete in general [20, 5, 19], the complexity drops to only PSPACE-complete for symmetric VASS [15]. As our main result, we confirm the immense drop in case of 2-CMs (in this case, symmetry amounts to invariance under all swaps of counters). We prove decidability of the configuration-to-configuration reachability problem, where one asks if a given machine has a sequence of steps starting in a given source configuration and ending in a given target one:
Theorem 1. The reachability problem is decidable for symmetric 2-counter machines.
Symmetric two-counter machines are thus not Turing-complete. We find this result quite surprising, as it applies to a model with restricted update instructions but unrestricted zero-test instructions. Interestingly, the converse restriction, namely imposing symmetry on zero-test transitions but not on update transitions, remains undecidable.
It is natural to consider invariance under subgroups of permutations: for every subgroup one can consider the class of -counter machines (-CMs), namely -counter machines invariant under all permutations from . On one end, when , the general definition instantiates to symmetric -CMs. On the opposite end, when is the trivial group one gets classical counter machines. Between the two extremes there is a landscape of models, whose expressive power is related according to the permutation subgroup relation: whenever , every -CM is automatically a -CM. For instance, every -CM is automatically a -CM, for the cyclic permutation group . As an additional result, we identify a bound on the impact of symmetry, already for 3-counter machines, namely we prove undecidability for -counter machines (even under an additional assumption that zero-tests are symmetric):
Theorem 2. The reachability problem is undecidable for -counter machines, for all .
Both the above results hold in the hardest case: decidability with unrestricted zero-tests, and undecidability with symmetric ones. This is unsurprising, as in § 8 we show that assuming symmetry of zero-tests does not weaken the model.
Open questions. A fundamental question is whether Theorem 1 extends to larger numbers of counters. In particular, is the reachability problem still decidable for symmetric 3-counter machines, whose update transitions are invariant under all 6 permutations of the 3 counters? Our decidability proof does not extend to 3 counters, as the argument relies on a number of low-dimensional properties of reachable sets and reachability relations. We thus leave this intriguing question for further research, conjecturing decidability for any number of counters:
Conjecture 3. The reachability problem is decidable for symmetric counter machines.
We focus on decidability, thus leaving open the exact complexity of the problem for symmetric 2-CMs. While we obtain an elementary upper bound for our decision procedure, the only lower bound is PSPACE-hardness inherited from symmetric 2-VASS [15]. It is possible that the reachability problem is PSPACE-complete in symmetric -CMs for every .
Symmetric CMs where the only update instructions are increments or decrements of a single counter, constitute a syntactic fragment of our setting. It remains to be established the expressive power of the fragment, and the complexity of its reachability problem.
Outline. Once we define the model in § 2, the subsequent § 3–§ 6 are devoted to the proof of Theorem 1. We proceed in a top-down manner, by consecutive reductions to more and more basic properties. In § 3 we provide the proof of Theorem 1, building on effective semilinearity of certain reachability sets and relations in a symmetric 2-CM. Then, in § 4 and 5, we prove the effective semilinearity, building on a structural property of target (resp. source) pumping in symmetric 2-VASS, that is subsequently shown in § 6. Technically, § 6 is probably the most intricate part of the paper, and the only one directly exploiting the symmetry of 2-CMs. In § 7, we turn to the proof of Theorem 2, followed by Section 8 where we discuss how syntactic restrictions of our model affect its expressive power. Finally, in Section 9, we provide an elementary upper bound on the complexity of our decision procedure for symmetric 2-CMs.
Related research. Identifying decidable restrictions of CMs is a very active line of research since the 1960s, for instance 1-counter, reversal-bounded, or restricted 2-counter machines [12, 14, 10]. A prominent example is CMs without zero-tests, that is vector addition systems with states (VASS), shown to have decidable reachability in the early 1980s [21, 17, 18]. The decidability extends to CMs with only one zero-tested counter [3], or with nested zero-tests [27, 11]. On the other hand, most natural restrictions preserve Turing-completeness, as long as no constraint is imposed on zero-tests. For instance, considering deterministic CMs, the reachability problem is still undecidable in the subclass of reversible CMs, where the step relation is reverse deterministic, and hence every step may be uniquely undone [24].
In the special case of 1 counter the symmetry requirement is void, and the reachability problem is NP-complete if transition updates are encoded in binary, and NL-complete in unary encoding [12]. The known complexity bounds separate symmetric 2-CMs from 1-CMs, the former being PSPACE-hard while the latter NP-complete, thus proving that symmetric 2-CMs are not (easily) simulated by 1-CMs.
Restricting the use of zero-tests in 2-CMs often leads not only to decidability, but even to PSPACE-completeness. Assuming binary encoding, the PSPACE-completeness has been obtained for 2-VASS [2, 1] (assuming unary encoding, we have NL-completeness [7]), but also for the further restriction to symmetric 2-VASS [15], and for a relaxation of 2-VASS to 2-CMs with just one zero-tested counter [9]. In all these cases the reachability relation is effectively semilinear, which is the key for obtaining a PSPACE upper bound, but which fails already for 3-VASS [13]. We do not know the exact complexity of symmetric 2-CMs. Neither do we know if the reachability relation of a symmetric 2-CM is semilinear, but we believe it is so.
Contrary to the above-mentioned restrictions of zero-tests, our model leaves the zero-tests unrestricted, which rarely results in a decidable model — the primary example being a result of Dudenhefner [6], showing that for certain choice of instruction set, the reversible 2-CMs become decidable, in contrast with [24].
Symmetric counter machines
Let be a positive integer. A -counter machine (-CM in short) is a finite-state automaton whose transitions may perform two kinds of instructions, namely update and zero-test instructions, on counters, namely nonnegative integer values stored as part of the configuration. Formally, we define such a machine as , where is a finite set of control states, is a finite set of transitions of , and the set of instructions is given by:
Execution of amounts to adding the vector to the counters, and execution of amounts to checking that counter has value . Formally, we define the semantics of by considering its configurations , written , and the step relation between configurations determined by transitions of : if
, for some , or
and , for some ,
where by we denote the -th coordinate of the vector . We use the term -VASS (vector addition system with states) for a -CM without zero-test instructions. The underlying VASS of is obtained by removing from all zero-test transitions.
The symmetric group acts naturally on vectors in and hence also on update transitions: for and , we define , where for every . A -CM is symmetric if its set of update transitions is invariant under the natural action: for every and , we have . Importantly, symmetry is imposed on update transitions, but not on zero-test transitions of . In the sequel we mostly focus on symmetric 2-CMs, namely 2-CMs whose set of update transitions is invariant under the swap of counters.
Remark 4. Likewise one defines -CMs, counter machines whose set of update transitions is invariant under the action of a permutation subgroup . Note that this notion is contravariant: when is a permutation subgroup of , every -CM is automatically a -CM, and not vice versa. We investigate this more general model only in Sections 7 and 8.
We define the reachability relation (between configurations) as the reflexive-transitive closure of . The reachability problem asks, given a CM and two of its configurations, a source and a target , whether (in which case we say that is reachable from ). A reachability certificate, namely any sequence of configurations
with and , related by the step relation, is said to be a run from to .
Variants. Two natural restrictions of the model are obtained by requiring that: (1) the set of zero-test transitions is also symmetric, that is invariant under permutations of counters; (2) all update transitions are single-counter, that is is nonzero on at most one coordinate. As we discuss later in Section 8, the first restriction is equally powerful as the unrestricted model, and imposing both restrictions makes the model essentially degenerate to 1-VASS, once the source and target vectors are zero. We do not know consequences of imposing solely the second restriction.
Outline of decidability proof
We now outline the proof of Theorem 1. To this end we fix a given symmetric 2-CM and two configurations: a source , and a target .
Notations. For relations , , we denote by the diagrammatic-order composition of the relations. In particular, whenever convenient we consider sets , as relations from/to the singleton set, denoting by and the (inverse) image of a set under a relation . The reflexive transitive closure of is denoted by , as usual.
Decomposing a run into segments. For convenience, we perform on the following notational preprocessing: we replace every zero-test transition by a sequence of two transitions,
where is a new state, unique to the transition . Notice that reachability in the new symmetric 2-CM thus obtained is equivalent to the original one, and that it has special states which can only be entered if the counter zero-tested by transition is zero; we call them zero-testing states. The zero-testing states have the property that they “remember” which counter is zero when the control of the machine is at them, and that zero-test transitions are exactly those entering a zero-testing state. A fragment (infix) of a run between two consecutive zero-testing states consists of only update transitions, except for the very last transition which is a zero-test. Such a fragment, called segment in the sequel, may be considered as a 2-VASS run that ends with one counter 0, and which counter is 0 is determined by the ending, zero-testing state. Formally, we will consider a segment to be a run in the underlying symmetric 2-VASS , leaving the final zero-test implicit in the fact that the final configuration of a segment has the relevant counter be zero.
Remark 5. Furthermore, w.l.o.g. we may assume that one counter is 0 in both source and target configurations. For instance, if the source configuration satisfies , we replace it by for a freshly added source state , and add an additional transition . We thus assume, w.l.o.g., that the source and target states are zero-testing.
In the decidability proof we exploit the unique decomposition of a run from source to target into segments:
where each starts and ends at consecutive zero-testing states of . Every is thus a run in the underlying 2-VASS , having one of the following forms:
where the initial and final states and are zero-testing states, and no zero-testing state is visited in between. Notice that we may write just without specifying which of the four cases occurs, since the (zero-testing) states , uniquely determine that. We follow the notational shorthand throughout and, instead of , which is a binary relation on , we prefer to use a binary relation on ,
where if and only if any of the four cases of (1) holds, namely the underlying 2-VASS has a corresponding run that does not visit zero-testing states except for the initial and final ones. In view of Remark 5, our task is to decide if for , that is whether a given pair belongs to the reflexive-transitive closure of .
Three types of segments. As we shall soon see, the relation can be split into three disjoint areas with different properties, delineated by a machine-dependent constant (see Figure 2). Thus, every segment , depending on the value of , falls into one of three categories, denoted by , , and . For a segment , we write:
Figure 2. The three relations , , and . The axes do not correspond to the counters, but rather the initial and final values and of a segment.
where the precise definition of the constant will be given in § 6. The reachability relation can now be expressed as
an arbitrary composition of the three sub-relations arbitrarily many times (note that the composition assures that control states match).
Using this categorization we split the run into three consecutive phases (each possibly empty):
, the prefix of ending with the last of the form ,
, an infix of consisting only of ’s of the form ,
, the remaining suffix of starting with the first remaining of the form .
Clearly, the composition of the three phases yields the reachability relation, that is
for the three relations defined by the following rational expressions:
Proof of Theorem 1. The proof uses semilinear sets. Any subset of of the form
for , is called a linear set with base and periods . A semilinear set is a finite union of linear sets in the same dimension . We say is semilinear if for every , the set is semilinear. Similarly, is semilinear if for every , the set is semilinear.
Theorem 1 is proved by showing that the relation , as well as the image of relation and inverse image of , are all effectively semilinear, i.e. they are semilinear sets whose descriptions are computable given the underlying 2-CM and source and target . Importantly, we only need to consider semilinear sets and relations in dimension .
Lemma 6. Given a 2-CM , the relation is effectively semilinear.
Lemma 7. Given a symmetric 2-CM and source and target , the sets
are effectively semilinear.
Remark 8. The proof of Lemma 6 does not use symmetry of a 2-CM and the lemma holds for all 2-CMs, as opposed to the proof of Lemma 7 that crucially uses the symmetry assumption.
Relying on the effective semilinearity given in Lemmas 6 and 7, the proof of Theorem 1 is immediate: the reachability question is, according to (3), equivalent to the nonemptiness of the intersection
of effectively semilinear sets, which is again effectively semilinear [4 Thm. 6]. It thus remains to demonstrate the two key lemmas. Continuing in a top-down manner, we first focus on Lemma 7, whose proof makes use of Lemma 6.
Effective semilinearity for and : Proof of Lemma 7
The target pumping property of segments of the form is a central technical tool in the proof of Lemma 7:
Lemma 9 (Target pumping). Given a symmetric 2-VASS , one can compute numbers such that for every pair of control states of and such that ,
Remark 10. The proof of Lemma 9, to be given in Section 6, is the (only) part of our development that unavoidably relies on symmetry. Lemma 9 fails for non-symmetric 2-VASS, for instance point fails for a 2-VASS with one state and one transition .
We apply Lemma 9 to the underlying symmetric 2-VASS of a given symmetric 2-CM . The four claims of Lemma 9 jointly imply that is target-pumpable, that is for every pair of zero-testing control states ,
The reverse version of the four claims of Lemma 9, where we swap source and target and reverse all transitions (the reverse of is , as expected), implies that is source-pumpable, that is
Note that we can assume the same in (6) and (7), by taking the least common multiple of the two constants given by the two applications of Lemma 9, and also the same , by taking the maximum of the two constants. In the sequel, fix the constant from (6) and (7).
Saturated sets. It is folklore that semilinear sets are exactly the ultimately periodic sets, i.e. those satisfying for some , , all and all sufficiently large . We call and a period and threshold of .
Given , we define -saturated subsets as those where for all , also . -saturated sets are ultimately periodic, and hence semilinear. An -saturated set is representable by a function that maps a state and remainder to the least number congruent to such that ,
and to if there is no such number . We call a period of , and the numbers appearing in the image of its bases. For instance, in consequence of (6) and (7), the image as well as the inverse image is always -saturated, regardless of .
For termination of our decision procedure it will be crucial that the semilinear sets it maintains form non-decreasing chains of -saturated sets , since we have:
Lemma 11. For every , every non-decreasing chain of of -saturated subsets of stabilizes.
Proof. The sequence is a non-increasing chain of functions, ordered pointwise (assuming for ), and hence necessarily stabilizes due to well-foundedness of the function space .
Before the proofs of Lemmas 6 and 7, a basic observation concerning individual segments:
Lemma 12. The relations , , are effectively semilinear.
Proof. The reachability relation of the underlying 2-VASS is effectively semilinear [2], which implies that so is , the restriction thereof enforcing a counter to be 0 initially or finally, and forbidding zero-testing states except the source and target ones. In consequence, its further restrictions , , , each of them obtained by intersecting with a semilinear set, are also effectively semilinear.
Proof of Lemma 7. Recall that . By Lemmas 6 and 12, both the relations and are effectively semilinear. By a standard argument building upon [4 Thm. 6], the composed relation is also effectively semilinear, in particular meaning that the set is semilinear for every given semilinear set . Furthermore, as is source pumpable (7), and therefore the composed relation is so as well, the set is always -saturated.
In order to argue that the set is effectively semilinear we make use of Lemma 11, iterating the transformation
starting from the initial set
until a fixpoint is reached. By the above observations, we deduce that both the initial set , as well as every successive iterate , are effectively semilinear and -saturated; moreover it is self-evident that the sequence is non-decreasing.
More explicitly, by Lemma 11 we have that at starting at some ,
Since both the iteration and the equality test are effective, the set
is effectively semilinear. We conclude the first part by noting that the proof is not specific to the starting set , and shows that is effectively semilinear given any semilinear , which will be useful in the second part.
Now we proceed to arguing that the set is effectively semilinear. To this aim we prefer to use another rational expression defining , where appears as a subexpression:
indeed, as in (4) in § 3, the inner subexpression describes an arbitrary composition of segments of type and that ends with one segment of type .
The structure of the proof is similar to the previous part, namely we proceed by iterating the relation defined by the inner subexpression, that is we consider the initial set and the consecutive iterates:
where
Similarly as before, knowing that is target pumpable, we know that all are -saturated sets, and therefore the sequence stabilizes, and hence
for some , similarly as before. The only missing ingredient is computability of the iteration . However, in order to apply the previously shown computability of the function
which proceeds ’backward’, for computability of the function which proceeds ’forward’, we need a trick. Note that the relation is always target-pumpable since is so by (6), and hence is always -saturated regardless of . To compute , one first establishes, for every state , which remainders modulo appear in this set, by applying the transformation (8) to the set
where , and checking nonemptiness of intersection with the set
Both the sets (9), (10) are effectively semilinear due to Lemmas 6 and 12, and hence the set , and its intersection with (10), are computable. Knowing which remainders to expect, one then finds the precise representation of by an exhaustive search. For every positively verified state-remainder pair , namely one with , one finds the least number such that and . For consecutive candidates , apply the transformation (8) to the set
and check nonemptiness of intersection with the set (10), until a nonempty intersection is found. This shows that the -saturated representation of may be computed, concluding the proof of the second part of Lemma 7.
Effective semilinearity of : Proof of Lemma 6
In outline, we prove that is essentially the reachability relation of an effectively constructible 1-CM , to which we apply Parikh’s theorem.
The key observation which makes the construction of possible, is that the relation is essentially one-dimensional: for any pair of zero-testing control states and , consider the set of pairs of initial and final counter values such that and . We may describe this set in one dimension, defining
Since the values of and together determine , the finite collection of sets fully describes the relation.
Moreover, each set is effectively semilinear, being the intersection of the effectively semilinear relation with the semilinear set , projected down to one dimension. Hence, each is ultimately periodic, with an effectively computable period and threshold . Define as the least common multiple of all the periods , across all choices of , and .
Control states of . Except for auxiliary states, to be clear from the construction below, the control states of are the control states of enriched with a number representing the remainder modulo of the current counter value:
We write , instead of , for the control state of corresponding to and remainder . As an invariant of our construction, counter values reachable in state in always satisfy .
The construction, to be detailed below, ensures the following correctness claim, for every pair of zero-testing control states and :
where and are the remainders of and modulo , respectively, and denotes the subset of the reachability relation of where all the intermediate states are auxiliary.
In other words, when is restricted to runs whose intermediate states are all auxiliary, it realizes the non-iterated relation of . Once this restriction is lifted, computes the iterated relation.
Transitions of . In control state , the 1-CM non-deterministically chooses a number , and a next zero-testing state , such that the current counter value belongs to the set as defined in (11). Upon positive test, increments the counter by and goes to the next state .
As the remainder of modulo is fixed and determined by , checking membership reduces to checking if (double by decrementing the counter by and then incrementing it by back) or checking if for some (double similarly, by decrementing the counter by , a zero-test, and incrementing the counter by back). Auxiliary states are used as intermediate states to perform the above steps.
This construction assures the equivalence (12). Considering now the unrestricted reachability relation of , for every zero-testing control states and ,
where and are the remainders of and modulo , respectively. The construction of is effective.
Effective semilinearity of $\mathrel{\Longrightarrow_{0}^{*}}. As 1-CMs are a special case of pushdown automata, we may now obtain Lemma 6 by Parikh’s Theorem: for each pair of zero-testing states , we build a pushdown automaton recognizing the language
or, equivalently,
Applying Parikh’s Theorem to this language, we’ll get that the relation is effectively semilinear [25, 8].
It remains to describe the construction of the aforementioned pushdown automata, which we depict on Figure 3. We extend the 1-CM to a labelled 1-CM, where every transition is labelled with a symbol from the alphabet , or with . Fix a pair of zero-testing states for which is to be recognized. Take all the transitions of as unlabelled (labelled with ), add extra states forming an -labelled cycle of transitions incrementing the counter by 1:

Figure 3. The construction we use to extract the language out of the 1-CM .
(which assures storing the remainder modulo in states), add another extra states forming a -labelled cycle of transitions decrementing the counter by 1:
and finally add 0-update transitions from to , and from to :
A labelled 1-CM extended in this manner recognizes the language when considered with initial configuration and final configuration . By the previous discussion, the lemma follows by Parikh’s theorem.
Target pumping: Proof of Lemma 9
We focus on proving point , noticing however that literally the same argument works for point . The other two points, namely and , follow immediately by swapping the coordinates.
To ease the presentation, we introduce the following definitions:
For a transition , the states are said to be the source and target of respectively, and the vector is said to be the effect of .
A path is a sequence of transitions such that the target of each transition matches the source of the next transition in the sequence. Unlike a run, a path does not fully specify the source and target configurations.
The source of the first transition is said to be the source of the path, and the target of the final transition is said to be the target of the path. The effect of a path is defined as the sum of the effects of its transitions.
A cycle is a path whose source and target coincide.
A path is said to be fireable at a configuration if there exists a configuration such that . This amounts to requiring that can be executed starting from , without the counters having to go negative along the way. We denote the target configuration thus obtained by .
For paths and , denote their concatenation by .
For a path , the transposed path is obtained by applying the symmetry assumption at each transition. If has effect , has effect .
We define the norm of a vector to be the maximal absolute value of its components, , and the norm of a 2-vass to be the maximal norm of the effects of its transitions, .
Proof of Lemma 9 . Consider a fixed symmetric 2-vass and a run for some . Assuming that the difference is sufficiently large (namely larger than some , depending only on ), we modify the run to lift the target configuration to for any and some particular , which depends on both and . Holding fixed, will only attain finitely many different values, hence we argue that taking the least common multiple of all yields a constant satisfying the claim of the lemma.
Denote by the sequence of transitions fired along the run , obtaining its corresponding path. According to the linear-path-scheme (LPS) decomposition of [2 Thm. 1], we may assume w.l.o.g. that is built of paths and cycles :
where the lengths of each path and cycle are at most , and both and are bounded by a polynomial of the the size of the unary representation of . Note that we do not claim any bound the number of iterations in of the cycles . Let be the minimal value such that every cycle of of length at most is fireable at . Call a cycle major if its number of iterations is larger than , and minor otherwise. W.l.o.g. we may assume that all cycles are major, by inlining any minor cycles into their neighboring one-off paths and . After this operation, the lengths of the one-off paths are bounded by .
Call a cycle sum-increasing if its effect satisfies . We claim that, by setting a large enough value of , we can guarantee that the run will contain at least one (major) sum-increasing cycle. Indeed, as we are assuming that , the sum of counters must increase by more than along . Thus, it is enough when
where and are the (polynomial in ) bounds on and , respectively.
We now focus our attention on the sum-increasing cycles, and perform case analysis in terms of the sign of each coordinate of their effect. Specifically, the effect of a sum-increasing cycle can be: vertical , horizontal , or one of , , or . We classify these into three cases (Figure 4, left).

Figure 4. A view of the space of effects of individual cycles. Left: An illustration of how the runs are split into three cases, based on the effects of the sum-increasing cycles present in the run. Cases 1–2 have priority, in that as long as at least one cycle in the relevant area is present, the run is handled by one of these cases. On the other hand, Case 3 is the fallback: it handles runs where all sum-increasing cycles fall in the area labeled “Case 3” (blue). Right: Proof strategy for Case 2. Given a cycle , we make use of the symmetry assumption to obtain the transposed cycle . The shaded area demarcates the effects we can obtain from linear combinations of and with positive coefficients. Observe that the shaded area contains the desired vertical effect (green, not to scale).
Case 1: Some sum-increasing cycle has vertical effect. One extra iteration of this cycle yields the claim, with the vertical effect of the cycle determining .
Case 2: Some sum-increasing cycle has effect or . Assume that has effect for some positive integers . Observe that . The case of effect is analogous.
As an outline, we will seek to increase the iteration count of the cycle , and introduce into the run the transposed cycle , such that the net effect of our modifications becomes vertical (see Figure 4, right).
For our argument it is enough if the is large enough to guarantee that somewhere in the middle of , the transposed cycle becomes fireable. We observe the following key claim, relying on the fact that the effect of is nonzero on both coordinates (in particular note that we do not use the sum-increasing assumption for this claim):
Claim 13. If is fireable at , then for any repetition count satisfying , the transposed cycle is fireable at ; .
Proof. The configurations at the boundaries between the iterations of within form an arithmetic progression given by . Observe that for we have
Recall now that, having eliminated all minor cycles by inlining, we must have . Thus, the range of values of admissible for Claim 13 is non-empty. Setting , we have that the transposed cycle is fireable after the first iterations of within . Equivalently, shifting the point of view one iteration earlier, the concatenation is fireable after .
Recall we have that , as the cycle is sum-increasing. Thus, the effect of , being , is positive on both coordinates, and may be fired arbitrarily many times in the middle of , without interference with the remainder of .
Now set . By iterating times the cycle , we get a cycle with effect , and then appending we get the desired vertical effect. Indeed, the effect of
is , and this cycle is still fireable in the middle of . We thus get the claim with .
Case 3: All sum-increasing cycles have or effect. Let us restrict our attention to those cycles , whose effect satisfies . Depending on whether or , we call such cycles horizontally positive, or horizontally negative respectively. Define the steepness of such cycles as , and denote it by . Note that, while in general the steepness may be negative, by assumption it will never be negative for a sum-increasing cycle (see Figure 5, left).

Figure 5. The steepness comparison central to the proof strategy of Case 3. Left: An illustration of the properties of steepness. The vectors represent the effects of three cycles , , and , where is horizontally positive, and the other two are horizontally negative. The cycle is steeper than , and is steeper than . Cycles whose effect lies within the area shaded green (resp. red) have positive (resp. negative) steepness. The area shaded gray corresponds to sum-increasing cycles that get handled in Case 2, and thus cannot occur in Case 3. Right: A sum-increasing cycle , with three candidates for a subsequent horizontally-negative cycle (cf. Claim 14), illustrated in terms of their combined effect. Observe how the vertical effect obtained this way is positive exactly when is steeper than .
We will now aim at increasing the repetition count of one of the sum-increasing cycles, together with one other cycle, occurring later in the run, in order to obtain a vertical effect (see Figure 5, right). That suitable cycles exist is stated by the following claim.
Claim 14. There are some such that is a sum-increasing cycle, is horizontally negative, and is steeper than (i.e. ).
Proof. Call a sum-increasing cycle record-breaking if it is steeper than all sum-increasing cycles that came before it, and suppose that the claim doesn’t hold. In outline, we will define a sequence of straight lines in the configuration space, each parallel to the effect of the most recent record-breaking cycle, such that the counter values will always stay below the current line (see Figure 6). We will then show that the supposed target configuration of the run is above all the invariant lines, to derive a contradiction.

Figure 6. A run prefix that does not yet satisfy Claim 14. Solid lines represent iterated cycles, and dotted lines represent one-off paths. Record-breaking cycles are drawn using thicker lines; the color of the cycle indicates whether the cycle increases or decreases the counter sum. Parallel to each record-breaking cycle, dashed lines represent the successive invariant lines, below which the configuration will stay. Note the target configuration , above both invariant lines.
For a cycle , denote by the steepness of the most recent record-breaking cycle, i.e.
with as the initial value. As one would expect, the value of will define the slope of each line. Concretely specifying the -intercept, however, requires a bit more work.
Define and to be the counter values the run achieves immediately before and after , respectively. Let be the index of the first sum-increasing cycle of the run. For , define as the sum of the norms of the effects of all one-off paths between and , i.e. writing for the sum of norms of transitions along a path ,
We extend the definitions in a natural way to where relevant: let be the counter values of the run’s target configuration, and denote by the sum of norms of effects of all one-off paths after , up to and including .
By induction on , we will now prove that the pair of counter values will always satisfy
Geometrically, this defines the dashed lines in Figure 6.
At , the inequality trivially holds. Suppose then that the inequality holds at a specific , aiming to prove it for .
We shall follow the structure of the run, aiming first to prove that after executing the effect of , the configuration stays below the same line, i.e.
See Figure 7 (left) for an illustration of this step. Symbolically, writing and , we see that our aim is to prove . The first case, easily handled, is when . Indeed, we handle cycles of vertical effect in Case 1, so if we encounter such a cycle here, then must hold.

Figure 7. A geometric intuition for why the inductive invariant gets preserved. Left: Horizontally positive cycles (green) stay below the invariant line, as by construction they are at most as steep as the invariant’s slope; horizontally negative cycles either stay below the invariant line (red) or satisfy Claim 14 (dotted black). Center: One-off paths may force the invariant line to be raised, but this can be bounded ahead of time. Right: Because the configuration is guaranteed to stay at , we may freely make the invariant line steeper as long as the -intercept doesn’t get lowered in the process.
In the interesting case where , we apply the definition of to express the desired inequality as , and consider the sign of . For a horizontally positive cycle, i.e. , we need . If is sum-increasing, this holds by definition; otherwise note .
Finally, let be a horizontally negative cycle. In that situation, we need . Let be the most recent record-breaking cycle before , which must exist, as (and is ruled out by being horizontally negative). Now note that if we had , cycles and would satisfy Claim 14. As we are assuming that the claim doesn’t hold, we indeed have , thereby establishing (16).
Our next focus shall be handling the effect of (Figure 7, center), proving that
With denoting the effect of the one-off path , we have , and analogously, . Comparing with (16), we see that it’ll suffice to show
(recall that ). As both and are bounded by , we have
Multiplying the latter by and adding the two inequalities together, we obtain
as required.
Having now established (17), it remains to raise the slope of the invariant line to (compare Figure 7, right). We note that , and moreover both and are nonnegative, so we have
This ends the induction, and so we get (15) up to and including . As is the final configuration, we have:
Let us now focus on establishing an upper bound for each expression occurring on the right-hand side. Firstly, we have , which should be clear from the definition of the latter. Next, note that for any cycle we have , and therefore .
Finally, for , we note that , and analyze the latter instead. Recall that are the counter values immediately before the first sum-increasing cycle of the run, so any increase above the initial counter sum of is fully attributable to the effects of the one-off paths before . Thus, we get . In summary, we obtain
As the assumption of the lemma is that , we can obtain a contradiction by setting
Take any cycles , where , as given by Claim 14. Their horizontal effects satisfy and , and hence the sum of the effects of and is vertical and equal for . Expanding with and with yields a run ending in , where . Moreover, this modification will never decrease any intermediate value of the counters, as compared to the original run . The proof of Case 3 is thus completed.
To summarize, in all the three cases the sufficiently large value of is . The proof of Lemma 9 is thus completed.
Undecidability for Z3-cms
We now turn to -counter machines, and prove that their reachability problem is undecidable, in contrast with symmetric 2-CMs. We proceed by reducing from the reachability problem of general 2-CMs, which is undecidable [23]. Our reduction readily generalizes to a reduction from general -CMs to -CMs, showing that reachability is undecidable in -CMs, for . For concreteness, however, we focus on the case of $n=3.
Proof of Theorem 2. Recall that a -CM is a 3-CM such that for any transition labeled by , the transitions and are also present between the same pair of states. Note however, that the -CM we construct here also satisfies a stronger condition: the zero-test transitions are symmetric as well, effectively testing that an unspecified counter is zero. We write this as zero-test().
For any 2-CM , we shall construct a -CM that simulates it, where is a copy of with auxiliary states adjoined.
For a configuration of , the corresponding configuration of shall have the form , with two main counters keeping track of the values of the counters of , and one auxiliary counter, which is always zero outside of auxiliary states. Thanks to the presence of the auxiliary counter, we will be able to “anchor” each transition as it executes, in such a way that any run making use of an unwanted cyclic rotation of a transition will get rapidly cut short by a failing zero-test.
To simulate a transition of the form , we include in the transitions in use by the following fragment of a run:
as well as their cyclic rotations. We now need to verify that the cyclic shifts of these transitions do not cause any issues.
Let us first consider the instruction. As the update vector contains only one zero, executing any cyclic rotation will disturb the auxiliary counter, making it non-zero. Moreover, because the main counters have a remainder of 2 mod 3 before the transition, they can only have a remainder of 1 or 2 after any cyclic rotation executes. In particular, none of the main counters may become zero. Hence, should any unwanted cyclic rotation of the first update instruction execute, the zero-test that follows will fail.
The reasoning for the instruction is similar: any cyclic rotation will increase the auxiliary counter to 1, and neither of the main counters may decrease to 0, as the vector is non-negative on all coordinates.
We now turn to simulating the zero-test transitions of . For concreteness, let us focus on the case where the first counter is being zero-tested; a zero-test of the second counter is handled analogously.
To simulate a transition of , performs the following steps:
As the instruction update has only one non-negative number, any of its other rotations will attempt to make the auxiliary counter negative, and thus will not be able to execute. Then, the first zero-test is performed. As the counters have remainders mod 3 respectively, this zero-test will only succeed when , exactly as required to simulate a zero-test instruction.
To finish simulating the zero-test, update undoes the modifications of the counters. As we now know that the first counter is zero, and all numbers in the update instruction are non-zero, we can infer that no rotation can leave the first counter at zero. Moreover, the second counter has a remainder 1 mod 3, therefore the sole negative number in the update instruction, having value , cannot make that counter be zero either. Thus, for the final zero-test to pass, it is the auxiliary counter that must become zero, and this can only happen if the is appropriately aligned, which rules out all unwanted rotations.
Variants
We now discuss the consequences of imposing the following restrictions on symmetric CMs:
the set of zero-test transitions is also symmetric, that is invariant under permutations of counters;
all update transitions are single-counter, that is is nonzero on at most one coordinate.
Symmetric zero-tests. For simplicity, let’s focus on 2-CMs first. Symmetric zero-test transitions, effectively testing that an unspecified counter is zero, written zero-test, can surprisingly simulate unrestricted ones. To this aim, a configuration of a symmetric 2-CM would be simulated by , thus doubling the counter values and distinguishing them by parity. Consequently, a transition is simulated a transition . Therefore the update transitions, even symmetric ones, preserve parity of both counters. Due to parity distinction, a transition checking if an unspecified counter is 0, in fact checks if counter 1 is 0. On the other hand, simulation of transition is done in three steps, using two auxiliary intermediate states :
Observe that the first and the last transition swap parity of counters, and likewise do their swapped versions. Therefore a successful zero-test is only possible on counter 2, which rules out possibility of use of swapped versions of the first and last transition.
The above considerations generalize to -CMs, for an arbitrary number of counters, and arbitrary permutation group . To this aim we distinguish between the counters by remainders modulo , simulate a configuration by
and simulate a transition by . Furthermore, to correctly simulate a zero-test of counter , say a transition , we replace the vectors and in the first and last transition in (18) by
respectively, where the unique value of negative (left) or positive (right) sign appears on the th coordinate.
Symmetric zero-tests and single-counter updates. We do not know how much weaker is the fragment with only single-counter update transitions (but unrestricted zero-test transitions). However, imposing both restrictions results in a degeneracy, namely the model of -cms, , is simulated by (and equivalent to) 1-vass, at least as long as zero source and target vectors are considered. Indeed, whenever a symmetric cm has a run , it also has a simple run, in which all counter updates are performed on counter 1, say, while all zero-tests are (trivially) performed on counter 2, say. The zero-tests are thus void, and simple runs are essentially runs of a 1-vass.
Complexity bound for thm:main
In this section we provide an upper complexity bound for our decision procedure outlined in Section 3. We will measure the size of input instances of the reachability problem as the size of the unary representation of a 2-cm , the source and the target , namely
where and are the sets of zero-test and update transitions of , respectively, and is the underlying 2-vass. Our objective is to provide an elementary upper bound in terms of , rather than optimizing the number of exponents, and we will be content with a 5-exponential bound.
Bounds for Lemma 9. We estimate the values of constants and . The constant
is polynomial in . The norm of the effect of every cycle of length at most is bounded by , where is the maximal length (polynomial in ), and hence all values appearing in all the three cases in the proof of Lemma 9 are bounded by , thus polynomially in . Taking as the least common multiple of all is enough for the claim of the lemma. In summary:
Claim 15. The constants and of Lemma 9 are bounded polynomially and exponentially in , respectively.
Terminology. We use the -exponential function , defined as , and . Whenever a base-period representation of a semilinear set is clear from the context, we write for the maximum of norms of bases and periods of this representation. In the sequel we say that a semilinear set is -exponentially semilinear if given , one can compute a base-period representation of of norm bounded by .
Bounds for Lemma 12. According to the linear-path-scheme decomposition of [2 Thm. 1], whenever a configuration is reachable from in the underlying 2-vass of , is also reachable from by a run
where is polynomial in , and are paths and are cycles of length polynomial in ((14)). As shown in [2], once , and are fixed, the reachability relation along all runs of the form (19) is the union of (the projections of) the solution sets of instances of the integer linear programming problem of size polynomial in , and hence effectively semilinear. Moreover, numbers appearing in are bounded exponentially in , and hence by the bound of [26] (see also [4 Prop. 4]), the norms of bases and periods of the reachability relation along all runs of the form (19) are bounded exponentially in . Summing over all choices of , and , we conclude that the reachability relation of is exponentially semilinear. The same applies to the relation , which is essentially the intersection of with a linear set fixing some coordinates to 0. Finally, we transfer the same effective bounds to the three subrelations by noticing that each of them is the intersection of with a semilinear set whose bases and periods are of norm at most , the constant of Lemma 9 (which is polynomial in ), and intersection of linear sets in fixed dimension (here 2) increases the norms of bases and periods at most polynomially (see [4 Thm. 6]):
Claim 16. Semilinear sets satisfy .
We have thus shown:
Claim 17. The relations are exponentially semilinear.
Bound for Lemma 6. By the above effective exponential bounds on bases and periods of , we conclude that sets (11) in the proof of Lemma 6 have base-period representations with at most exponential periods and bases. The period and threshold of ultimately periodic presentation of are at most doubly exponential, as they are bounded by the least common multiplicity of bases and periods of its base-period representation. So is the least common multiple of all periods of , across all choices of , and , which is doubly exponential. In consequence, the 1-cm constructed in the proof of Lemma 6 is at most doubly exponentially large. This, combined with the exponential blow-up of Parikh’s theorem [16 Thm. 11], yields a triple-exponential bound on the norms of bases and periods of the relation . As both construction of and Parikh’s theorem are effective, we have thus shown:
Claim 18. The relation is 3-exponentially semilinear.
Bound for Lemma 7. Composition of two semilinear relations in fixed dimension, very much like intersection, increases the norms of bases and periods at most polynomially:
Claim 19. Semilinear relations satisfy .
Indeed, ignoring for simplicity, Claim 19 follows immediately from [4 Thm. 6], similarly to Claim 16, as the composition is the projection to the first and last coordinate of .
Likewise we get the bound for images and inverse images of relations:
Claim 20. Semilinear relations and semilinear sets satisfy .
Concerning the first part of Lemma 7, we bound the number of iterations of the transformation
needed to compute the fixpoint , starting from . Due to Claims 18 and 20, the bases of the -saturated set are bounded triply exponentially in . Then every base of every next -saturated set
as , is either smaller than some base of , or is newly created, namely while for some and . A newly created base may appear at most times (exponentially many times) during the whole iteration. Again due to Claims 18 and 20, if a new base appears in then
otherwise . In consequence, for every we have
which yields a triply exponential bound on . Therefore, the total number of iterations of (20) before a fixpoint is reached is at most triply exponential as well. Our reasoning was not specific to the starting set , and we have actually shown:
Claim 21. Given a -exponentially semilinear set , , the set is -exponentially semilinear and computable in at most -exponentially many iterations of (20).
Concerning the second part of Lemma 7, we need to bound the number of iterations of the transformation
needed to compute the fixpoint , starting from . We should also provide an upper bound on computation of , and computation of every iteration .
We start by analyzing the computation of . By Claim 17 the set is exponentially semilinear. Then by Claim 21 applied to and , the set is computable in at most triply exponentially many iterations of the transformation (20), say iterations. Then intersection of with the set ,
has (relying on Claims 18 and 16) bases and periods of at most triply exponential norm. Assume, w.l.o.g., that for some doubly exponential , and let . The relation is computable by -fold self-composition starting from , each self-composition increasing the norm polynomially, which implies:
Claim 22. The relation is 4-exponentially semilinear.
We have . Now, a key observation is that once is nonempty, there is a pair such that , which implies that the set
has necessarily nonempty intersection with , and moreover the intersection contains, due to Claims 17, 19, 20 and 22, a number which is at most 4-exponential in . This provides a 4-exponential upper bound on the number of iterations of the exhaustive search in the proof of Lemma 7, and thus also the same bound on . Testing candidates in the exhaustive search requires only 4-exponentially many iterations of (20), due to Claim 21 (applied to ).
When computing the iteration , we only apply Claim 21 to sets of the form , which do not themselves depend on the input set . As such, the bound on the number of iterations does not depend on the input set either, and in the same way as above we obtain the same 4-exponential bound on the norm of every subsequent iterate .
Finally, the 4-exponential bound on the number of iterations (22) before a fixpoint is reached is shown similarly as in the first part. Similarly as in (21) we have
which yields a 4-exponential bound on . This completes the complexity analysis of the second part of Lemma 7.
To summarize, we have obtained the bounds on the norms of representations of computed semilinear sets, and on the numbers of iterations performed in the course of computation. The bounds are 4-exponential in , the size of unary representation, and hence at 5-exponential in the size of binary representation. Combined with an exponential blowup incurred by a necessity to generate all bases and periods, this yields the elementary running time of our decision procedure. As the only known lower bound is PSPACE-hardness (in binary representation), narrowing the apparent complexity gap is left as future research.
References
- [1]Michael Blondin, Matthias Englert, Alain Finkel, Stefan Göller, Christoph Haase, Ranko Lazic, Pierre McKenzie, and Patrick Totzke. The reachability problem for two-dimensional vector addition systems with states. J. ACM, 68(5):34:1–34:43, 2021. doi:10.1145/3464794.DOI
- [2]Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, and Pierre McKenzie. Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete. In Proceedings of LICS 2015, pages 32–43, 2015. doi:10.1109/LICS.2015.14.DOI
- [3]Rémi Bonnet. The reachability problem for vector addition system with one zero-test. In Proc. MFCS 2011, volume 6907 of Lecture Notes in Computer Science, pages 145–157. Springer, 2011. doi:10.1007/978-3-642-22993-0\_16.DOI
- [4]Dmitry Chistikov and Christoph Haase. The Taming of the Semi-Linear Set. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 128:1–128:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016.DOI
- [5]Wojciech Czerwiński and Łukasz Orlikowski. Reachability in Vector Addition Systems is Ackermann-complete. In Proceedings of FOCS 2021, pages 1229–1240. IEEE, 2021. doi:10.1109/FOCS52979.2021.00120.DOI
- [6]Andreј Denhefner. Certified decision procedures for two-counter machines. In Amy P. Felty, editor, Proc. FSCD 2022, volume 228 of LIPIcs, pages 16:1–16:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.FSCD.2022.16, doi:10.4230/LIPIcs.FSCD.2022.16.
- [7]Matthias Englert, Ranko Lazic, and Patrick Totzke. Reachability in two-dimensional unary vector addition systems with states is NL-complete. In Proc. LICS 2016, pages 477–484. ACM, 2016. doi:10.1145/2933575.2933577.DOI
- [8]Javier Esparza, Pierre Ganty, Stefan Kiefer, and Michael Luttenberger. Parikh’s theorem: A simple and direct automaton construction. Information Processing Letters, 111(12):614–619, 2011. doi:10.1016/j.ipl.2011.03.019.DOI
- [9]Alain Finkel, Jérôme Leroux, and Grégoire Sutre. Reachability for two-counter machines with one test and one reset. In Proc. FSTTCS, volume 122 of LIPIcs, pages 31:1–31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.31, doi:10.4230/LIPIcs.FSTTCS.2018.31.
- [10]Alain Finkel and Grégoire Sutre. Decidability of reachability problems for classes of two counters automata. In Proc. STACS 2000, volume 1770 of Lecture Notes in Computer Science, pages 346–357. Springer, 2000. doi:10.1007/3-540-46541-3\_29.DOI
- [11]Roland Guttenberg, Wojciech Czerwiński, and Sławomir Lasota. Reachability and related problems in vector addition systems with nested zero tests. In Proc. LICS 2025, pages 581–593. IEEE, 2025. doi:10.1109/LICS65433.2025.00050.DOI
- [12]Christoph Haase, Stephan Kreutzer, Joël Ouaknine, and James Worrell. Reachability in succinct and parametric one-counter automata. In Proc. CONCUR 2009, volume 5710 of Lecture Notes in Computer Science, pages 369–383. Springer, 2009. doi:10.1007/978-3-642-04081-8\_25.DOI
- [13]John Hopcroft and Jean-Jacques Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 8(2):135–159, 1979. doi:10.1016/0304-3975(79)90041-0.DOI
- [14]Oscar H. Ibarra. Reversal-bounded multicounter machines and their decision problems. J. ACM, 25(1):116–133, 1978. doi:10.1145/322047.322058.DOI
- [15]Łukasz Kamiński and Sławomir Lasota. Reachability in symmetric VASS. In Proc. MFCS 2025, LIPIcs, pages 60:1–60:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.MFCS.2025.60.DOI
- [16]E. Kopczyński and A. W. To. Parikh images of grammars: Complexity and applications. In Proc. of LICS’10, pages 80–89, July 2010. doi:10.1109/LICS.2010.21.DOI
- [17]S. Rao Kosaraju. Decidability of reachability in vector addition systems (preliminary version). In Proc. STOC 1982, pages 267–281, 1982. doi:10.1145/800070.802201.
- [18]Jean-Luc Lambert. A structure to decide reachability in Petri nets. Theor. Comput. Sci., 99(1):79–104, 1992. doi:10.1016/0304-3975(92)90173-D.DOI
- [19]Jérôme Leroux. The Reachability Problem for Petri Nets is Not Primitive Recursive. In Proceedings of FOCS 2021, pages 1241–1252. IEEE, 2021. doi:10.1109/FOCS52979.2021.00121.DOI
- [20]Jérôme Leroux and Sylvain Schmitz. Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension. In Proceedings of LICS 2019, pages 1–13. IEEE, 2019. doi:10.1109/LICS.2019.8785796.DOI
- [21]Ernst W. Mayr. An algorithm for the general Petri net reachability problem. In Proc. STOC 1981, pages 238–246, 1981. doi:10.1145/800076.802477.DOI
- [22]Marvin Minsky. Recursive unsolvability of post’s problem of "tag" and other topics in theory of Turing machines. Annals of Mathematics, pages 437–455, 1961.DOI
- [23]Marvin Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967.
- [24]Kenichi Morita. Universality of a reversible two-counter machine. Theor. Comput. Sci., 168(2):303–320, 1996. doi:10.1016/S0304-3975(96)00081-3.DOI
- [25]Rohit Parikh. On context-free languages. J. ACM, 13(4):570–581, 1966.DOI
- [26]Loïc Pottier. Minimal Solutions of Linear Diophantine Systems: Bounds and Algorithms. In Rewriting Techniques and Applications, 4th International Conference, RTA-91, Como, Italy, April 10-12, 1991, Proceedings, volume 488 of Lecture Notes in Computer Science, pages 162–173. Springer, 1991.DOI
- [27]Klaus Reinhardt. Reachability in Petri nets with inhibitor arcs. In Proc. RP 2008, volume 223 of Electronic Notes in Theoretical Computer Science, pages 239–264. Elsevier, 2008.DOI
