betaFeedback

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 (q,i,q′)(q,i,q') of a machine changes its state from qq to q′q', and executes an attached instruction ii. 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 σ\sigma of counters: for every update transition (q,i,q′)(q,i,q'), the machine has also a transition (q,σ(i),q′)(q,\sigma(i),q'), where σ\sigma acts on an update instruction ii 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.

Example symmetric 2-counter machine

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 (p,update⁡(−1,3),p)(p,\operatorname{update}(-1,3),p) transition also forces (p,update⁡(3,−1),p)(p,\operatorname{update}(3,-1),p) to exist. In contrast, we permit zero-test(1)(1) without a corresponding zero-test(2)(2) transition. Also notice the update(1,1)(1,1) 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 G≤SdG \le S_d one can consider the class of GG-counter machines (GG-CMs), namely dd-counter machines invariant under all permutations from GG. On one end, when G=SdG = S_d, the general definition instantiates to symmetric dd-CMs. On the opposite end, when GG 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 G≤HG \le H, every HH-CM is automatically a GG-CM. For instance, every S3S_3-CM is automatically a Z3\mathbb{Z}_3-CM, for the cyclic permutation group Z3≤S3\mathbb{Z}_3 \le S_3. As an additional result, we identify a bound on the impact of symmetry, already for 3-counter machines, namely we prove undecidability for Z3\mathbb{Z}_3-counter machines (even under an additional assumption that zero-tests are symmetric):

Theorem 2. The reachability problem is undecidable for Zd\mathbb{Z}_d-counter machines, for all d≥3d \ge3.

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 dd-CMs for every d≥2d \ge2.

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 dd be a positive integer. A dd-counter machine (dd-CM in short) M\mathcal{M} is a finite-state automaton whose transitions may perform two kinds of instructions, namely update and zero-test instructions, on dd counters, namely nonnegative integer values stored as part of the configuration. Formally, we define such a machine as M=(Q,T)\mathcal{M} = (Q,T), where QQ is a finite set of control states, T⊆Q×I×QT \subseteq Q \times\mathcal{I} \times Q is a finite set of transitions of M\mathcal{M}, and the set I\mathcal{I} of instructions is given by:

I={update(w)∣w∈Zd}∪{zero-test(i)∣i∈{1…d}}.\mathcal{I} = \{\mathbf{update}(\mathbf{w}) \mid\mathbf{w} \in\mathbb{Z}^{d}\} \cup\{\mathbf{zero\text{-}test}(i) \mid i \in\{1 \ldots d\}\}.

Execution of update(w)\mathbf{update}(\mathbf{w}) amounts to adding the vector w\mathbf{w} to the counters, and execution of zero-test(i)\mathbf{zero\text{-}test}(i) amounts to checking that counter ii has value 00. Formally, we define the semantics of M\mathcal{M} by considering its configurations (q,v)∈Q×N(q,\mathbf{v}) \in Q \times\mathbb{N}, written q(v)q(\mathbf{v}), and the step relation between configurations determined by transitions of M\mathcal{M}: q(v)⟶q′(v′)q(\mathbf{v}) \longrightarrow q'(\mathbf{v}') if

  • v′=v+w\mathbf{v}' = \mathbf{v} + \mathbf{w}, for some (q,update(w),q′)∈T(q,\mathbf{update}(\mathbf{w}),q') \in T, or

  • v′=v\mathbf{v}' = \mathbf{v} and v[i]=0\mathbf{v}[i] = 0, for some (q,zero-test(i),q′)∈T(q,\mathbf{zero\text{-}test}(i),q') \in T,

where by v[i]\mathbf{v}[i] we denote the ii-th coordinate of the vector v\mathbf{v}. We use the term dd-VASS (vector addition system with states) for a dd-CM without zero-test instructions. The underlying VASS of M\mathcal{M} is obtained by removing from M\mathcal{M} all zero-test transitions.

The symmetric group SdS_d acts naturally on vectors in Zd\mathbb{Z}^d and hence also on update transitions: for σ∈Sd\sigma\in S_d and t=(q,update⁡(w),q′)∈Tt = (q,\operatorname{update}(\mathbf{w}),q') \in T, we define σ(t)=(q,update⁡(σ(w)),q′)\sigma(t) = (q,\operatorname{update}(\sigma(\mathbf{w})),q'), where σ(w)[σ(i)]=w[i]\sigma(\mathbf{w})[\sigma(i)] = \mathbf{w}[i] for every i∈{1…d}i \in\{1 \ldots d\}. A dd-CM M\mathcal{M} is symmetric if its set of update transitions is invariant under the natural action: for every σ∈Sd\sigma\in S_d and (q,update⁡(w),q′)∈T(q,\operatorname{update}(\mathbf{w}),q') \in T, we have (q,update⁡(σ(w)),q′)∈T(q,\operatorname{update}(\sigma(\mathbf{w})),q') \in T. Importantly, symmetry is imposed on update transitions, but not on zero-test transitions of M\mathcal{M}. 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 GG-CMs, counter machines whose set of update transitions is invariant under the action of a permutation subgroup G≤SdG \leq S_d. Note that this notion is contravariant: when GG is a permutation subgroup of HH, every HH-CM is automatically a GG-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 ⟶∗\mathrel{\longrightarrow^{*}} of ⟶\longrightarrow. The reachability problem asks, given a CM M\mathcal{M} and two of its configurations, a source s∈Q×Nds \in Q \times\mathbb{N}^{d} and a target t∈Q×Ndt \in Q \times\mathbb{N}^{d}, whether s⟶∗ts \mathrel{\longrightarrow^{*}} t (in which case we say that tt is reachable from ss). A reachability certificate, namely any sequence ρ\rho of configurations

q0(v0)⟶q1(v1)⟶⋯⟶qn(vn)q_0(\mathbf{v}_0) \longrightarrow q_1(\mathbf{v}_1) \longrightarrow\cdots\longrightarrow q_n(\mathbf{v}_n)

with s=q0(v0)s = q_0(\mathbf{v}_0) and t=qn(vn)t = q_n(\mathbf{v}_n), related by the step relation, is said to be a run from ss to tt.

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 (q,update⁡(w),q′)(q,\operatorname{update}(\mathbf{w}),q') are single-counter, that is w\mathbf{w} 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 M=(Q,T)\mathcal{M} = (Q,T) and two configurations: a source ss, and a target tt (s,t∈Q×N2)(s,t \in Q \times\mathbb{N}^2).

Notations. For relations R⊆A×BR \subseteq A \times B, R′⊆B×CR' \subseteq B \times C, we denote by R∘R′⊆A×CR \mathbin{\circ} R' \subseteq A \times C the diagrammatic-order composition of the relations. In particular, whenever convenient we consider sets S⊆AS \subseteq A, T⊆BT \subseteq B as relations from/to the singleton set, denoting by S∘R⊆BS \mathbin{\circ} R \subseteq B and R∘T⊆CR \mathbin{\circ} T \subseteq C the (inverse) image of a set under a relation RR. The reflexive transitive closure of R⊆A×AR \subseteq A \times A is denoted by R∗R^{*}, as usual.

Decomposing a run into segments. For convenience, we perform on M\mathcal{M} the following notational preprocessing: we replace every zero-test transition t=(q,zero-test⁡(i),q′)∈Tt = (q,\operatorname{zero-test}(i),q') \in T by a sequence of two transitions,

(q,zero-test⁡(i),qt)(qt,update⁡(0,0),q′),(q,\operatorname{zero-test}(i),q_t) \qquad(q_t,\operatorname{update}(0,0),q'),

where qtq_t is a new state, unique to the transition tt. Notice that reachability in the new symmetric 2-CM thus obtained is equivalent to the original one, and that it has special states qtq_t which can only be entered if the counter zero-tested by transition tt 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 V\mathcal{V}, 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 q(v1,v2)q(v_1,v_2) satisfies 0<v1≤v20<v_1\le v_2, we replace it by qs(0,v2−v1)q_s(0,v_2-v_1) for a freshly added source state qsq_s, and add an additional transition (qs,update(v1,v1),q)(q_s,\mathbf{update}(v_1,v_1),q). 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 ρ\rho from source ss to target tt into segments:

ρ=ρ0ρ1…ρn,\rho=\rho_0\rho_1\ldots\rho_n,

where each ρi\rho_i starts and ends at consecutive zero-testing states of ρ\rho. Every ρi\rho_i is thus a run in the underlying 2-VASS V\mathcal{V}, having one of the following forms:

q(a,0)⟶∗q′(0,a′)q(0,a)⟶∗q′(a′,0)q(0,a)⟶∗q′(0,a′)q(a,0)⟶∗q′(a′,0).(1)\begin{aligned} q(a,0)&\mathrel{\longrightarrow^{*}}q'(0,a') & q(0,a)&\mathrel{\longrightarrow^{*}}q'(a',0)\\ q(0,a)&\mathrel{\longrightarrow^{*}}q'(0,a') & q(a,0)&\mathrel{\longrightarrow^{*}}q'(a',0). \tag*{(1)} \end{aligned}

where the initial and final states qq and q′q' are zero-testing states, and no zero-testing state is visited in between. Notice that we may write just q(a)⟶∗q′(a′)q(a)\mathrel{\longrightarrow^{*}}q'(a') without specifying which of the four cases occurs, since the (zero-testing) states qq, q′q' uniquely determine that. We follow the notational shorthand throughout and, instead of ⟶∗\mathrel{\longrightarrow^{*}}, which is a binary relation on Q×N2Q\times\mathbb{N}^2, we prefer to use a binary relation on Q×NQ\times\mathbb{N},

⟹ ⊆(Q×N)2,\mathrel{\Longrightarrow}\ \subseteq(Q\times\mathbb{N})^2,

where q(a)⟹q′(a′)q(a)\mathrel{\Longrightarrow}q'(a') if and only if any of the four cases of (1) holds, namely the underlying 2-VASS V\mathcal{V} 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 s⟹∗ts\mathrel{\Longrightarrow^{*}}t for s,t∈Q×Ns,t\in Q\times\mathbb{N}, that is whether a given pair (s,t)(s,t) belongs to the reflexive-transitive closure of ⟹\mathrel{\Longrightarrow}.

Three types of segments. As we shall soon see, the relation ⟹\mathrel{\Longrightarrow} can be split into three disjoint areas with different properties, delineated by a machine-dependent constant CC (see Figure 2). Thus, every segment ρi:q(a)⟹q′(a′)\rho_i:q(a)\mathrel{\Longrightarrow}q'(a'), depending on the value of a−a′a-a', falls into one of three categories, denoted by ⟹+\mathrel{\Longrightarrow}_+, ⟹−\mathrel{\Longrightarrow}_-, and ⟹0\mathrel{\Longrightarrow}_0. For a segment q(a)⟹q′(a′)q(a)\mathrel{\Longrightarrow}q'(a'), we write:

Figure 2. The three relations ⟹+\Longrightarrow_{+}, ⟹−\Longrightarrow_{-}, and ⟹0\Longrightarrow_{0}. The axes do not correspond to the counters, but rather the initial and final values aa and a′a' of a segment.

q(a)⟹+q′(a′),if a′>a+C;q(a)⟹−q′(a′),if a>a′+C;q(a)⟹0q′(a′),if ∣a−a′∣≤C.(2)\begin{aligned} q(a)&\mathrel{\Longrightarrow}_+q'(a'), &&\text{if }a'>a+C;\\ q(a)&\mathrel{\Longrightarrow}_-q'(a'), &&\text{if }a>a'+C;\\ q(a)&\mathrel{\Longrightarrow}_0q'(a'), &&\text{if }\lvert a-a'\rvert\le C. \tag*{(2)} \end{aligned}

where the precise definition of the constant CC will be given in § 6. The reachability relation can now be expressed as

⟹∗=(⟹0∪⟹−∪⟹+)∗,\mathrel{\Longrightarrow^{*}}=\left(\mathrel{\Longrightarrow}_0\mathbin{\cup}\mathrel{\Longrightarrow}_-\mathbin{\cup}\mathrel{\Longrightarrow}_+\right)^{*},

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 ρ\rho into three consecutive phases (each possibly empty):

  • Φ1\Phi_1, the prefix of ρ\rho ending with the last ρi\rho_i of the form ⟹+\Longrightarrow_{+},

  • Φ2\Phi_2, an infix of ρ\rho consisting only of ρi\rho_i’s of the form ⟹0\Longrightarrow_{0},

  • Φ3\Phi_3, the remaining suffix of ρ\rho starting with the first remaining ρi\rho_i of the form ⟹−\Longrightarrow_{-}.

Clearly, the composition of the three phases yields the reachability relation, that is

⟹∗=Φ1∘Φ2∘Φ3,(3)\Longrightarrow^{*} = \Phi_1 \circ\Phi_2 \circ\Phi_3, \tag*{(3)}

for the three relations defined by the following rational expressions:

Φ1=((⟹0∪⟹−)∗∘⟹+)∗,Φ2=⟹0∗,Φ3=(⟹−∘⟹0∗)∗.(4)\begin{aligned} \Phi_1 &= ((\Longrightarrow_{0} \cup\Longrightarrow_{-})^{*} \circ\Longrightarrow_{+})^{*},\\ \Phi_2 &= \Longrightarrow_{0}^{*},\\ \Phi_3 &= (\Longrightarrow_{-} \circ\Longrightarrow_{0}^{*})^{*}. \tag*{(4)} \end{aligned}

Proof of Theorem 1. The proof uses semilinear sets. Any subset of Nd\mathbb{N}^{d} of the form

{b+k1p1+⋯+knpn∣k1,…,kn∈N},(5)\{ b + k_1p_1 + \cdots+ k_np_n \mid k_1, \ldots, k_n \in\mathbb{N} \}, \tag*{(5)}

for b,p1,…,pn∈Ndb,p_1,\ldots,p_n \in\mathbb{N}^{d}, is called a linear set with base bb and periods p1,…,pnp_1,\ldots,p_n. A semilinear set is a finite union of linear sets in the same dimension dd. We say X⊆Q×NdX \subseteq Q \times\mathbb{N}^{d} is semilinear if for every q∈Qq \in Q, the set {n∣(q,n)∈X}⊆Nd\{n \mid(q,n) \in X\} \subseteq\mathbb{N}^{d} is semilinear. Similarly, R⊆(Q×Nd)2R \subseteq(Q \times\mathbb{N}^{d})^{2} is semilinear if for every q,q′∈Qq,q' \in Q, the set {(n,n′)∣((q,n),(q′,n′))∈R}⊆N2d\{(n,n') \mid((q,n),(q',n')) \in R\} \subseteq\mathbb{N}^{2d} is semilinear.

Theorem 1 is proved by showing that the relation Φ2\Phi_2, as well as the image of relation Φ1\Phi_1 and inverse image of Φ3\Phi_3, are all effectively semilinear, i.e. they are semilinear sets whose descriptions are computable given the underlying 2-CM M\mathcal{M} and source and target s,t∈Q×Ns,t \in Q \times\mathbb{N}. Importantly, we only need to consider semilinear sets and relations in dimension d=1d=1.

Lemma 6. Given a 2-CM M\mathcal{M}, the relation Φ2⊆(Q×N)2\Phi_2 \subseteq(Q \times\mathbb{N})^2 is effectively semilinear.

Lemma 7. Given a symmetric 2-CM M\mathcal{M} and source ss and target tt, the sets

Φ3∘{t}:={y∣(y,t)∈Φ3}⊆Q×N,\Phi_3 \circ\{t\} := \{y \mid(y,t) \in\Phi_3\} \subseteq Q \times\mathbb{N},
{s}∘Φ1:={x∣(s,x)∈Φ1}⊆Q×N\{s\} \circ\Phi_1 := \{x \mid(s,x) \in\Phi_1\} \subseteq Q \times\mathbb{N}

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 s⟹∗ts \mathrel{\Longrightarrow^{*}} t is, according to (3), equivalent to the nonemptiness of the intersection

({s}∘Φ1)×(Φ3∘{t})∩Φ2(\{s\} \circ\Phi_1) \times(\Phi_3 \circ\{t\}) \cap\Phi_2

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 Φ1\Phi_1 and Φ3\Phi_3: Proof of Lemma 7

The target pumping property of segments of the form ⟹+\mathrel{\Longrightarrow^{+}} is a central technical tool in the proof of Lemma 7:

Lemma 9 (Target pumping). Given a symmetric 2-VASS V\mathcal{V}, one can compute numbers C,D>0C,D>0 such that for every pair of control states q,q′q,q' of V\mathcal{V} and a,a′∈Na,a' \in\mathbb{N} such that a′>a+Ca' > a+C,

(1→2)if q(a,0)⟶∗q′(0,a′) then q(a,0)⟶∗q′(0,a′+D),(2→2)if q(0,a)⟶∗q′(0,a′) then q(0,a)⟶∗q′(0,a′+D),(2→1)if q(0,a)⟶∗q′(a′,0) then q(0,a)⟶∗q′(a′+D,0),(1→1)if q(a,0)⟶∗q′(a′,0) then q(a,0)⟶∗q′(a′+D,0).\begin{aligned} (1\to2)\quad&\text{if } q(a,0) \mathrel{\longrightarrow^{*}} q'(0,a') \text{ then } q(a,0) \mathrel{\longrightarrow^{*}} q'(0,a'+D),\\ (2\to2)\quad&\text{if } q(0,a) \mathrel{\longrightarrow^{*}} q'(0,a') \text{ then } q(0,a) \mathrel{\longrightarrow^{*}} q'(0,a'+D),\\ (2\to1)\quad&\text{if } q(0,a) \mathrel{\longrightarrow^{*}} q'(a',0) \text{ then } q(0,a) \mathrel{\longrightarrow^{*}} q'(a'+D,0),\\ (1\to1)\quad&\text{if } q(a,0) \mathrel{\longrightarrow^{*}} q'(a',0) \text{ then } q(a,0) \mathrel{\longrightarrow^{*}} q'(a'+D,0). \end{aligned}

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 (1→2)(1\to2) fails for a 2-VASS with one state qq and one transition (q,(−1,2),q)(q,(-1,2),q).

We apply Lemma 9 to the underlying symmetric 2-VASS V\mathcal{V} of a given symmetric 2-CM M\mathcal{M}. The four claims of Lemma 9 jointly imply that ⟹+\mathrel{\Longrightarrow^{+}} is target-pumpable, that is for every pair of zero-testing control states q,q′q,q',

q(a)⟹+q′(a′)⟹q(a)⟹+q′(a′+D).(6)q(a) \mathrel{\Longrightarrow^{+}} q'(a') \quad\Longrightarrow\quad q(a) \mathrel{\Longrightarrow^{+}} q'(a'+D). \tag*{(6)}

The reverse version of the four claims of Lemma 9, where we swap source and target and reverse all transitions (the reverse of (q,w,q′)(q,\mathbf{w},q') is (q′,−w,q)(q',-\mathbf{w},q), as expected), implies that ⟹−\mathrel{\Longrightarrow^{-}} is source-pumpable, that is

q(a)⟹−q′(a′)⟹q(a+D)⟹−q′(a′).(7)q(a) \mathrel{\Longrightarrow^{-}} q'(a') \quad\Longrightarrow\quad q(a+D) \mathrel{\Longrightarrow^{-}} q'(a'). \tag*{(7)}

Note that we can assume the same DD 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 CC, by taking the maximum of the two constants. In the sequel, fix the constant DD from (6) and (7).

Saturated sets. It is folklore that semilinear sets X⊆Q×NX \subseteq Q \times\mathbb{N} are exactly the ultimately periodic sets, i.e. those satisfying q(a)∈X⟺q(a+N)∈Xq(a) \in X \Longleftrightarrow q(a+N) \in X for some N>0N>0, M≥0M \ge0, all q∈Qq \in Q and all sufficiently large a≥Ma \ge M. We call NN and MM a period and threshold of XX.

Given N>0N>0, we define NN-saturated subsets X⊆Q×NX \subseteq Q \times\mathbb{N} as those where for all (q,a)∈X(q,a) \in X, also (q,a+N)∈X(q,a+N) \in X. NN-saturated sets are ultimately periodic, and hence semilinear. An NN-saturated set XX is representable by a function MIN⁡(X):Q×{0…N−1}→N∪{∞}\operatorname{MIN}(X): Q \times\{0 \ldots N-1\} \to\mathbb{N} \cup\{\infty\} that maps a state q∈Qq \in Q and remainder r<Nr < N to the least number nn congruent to rr such that (q,n)∈X(q,n) \in X,

MIN⁡(X)(q,r)=min⁡{n∣(q,n)∈X, n≡r mod N},\operatorname{MIN}(X)(q,r) = \min\{n \mid(q,n) \in X,\ n \equiv r \bmod N\},

and to ∞\infty if there is no such number nn. We call NN a period of XX, and the numbers n<∞n < \infty appearing in the image of MIN⁡(X)\operatorname{MIN}(X) its bases. For instance, in consequence of (6) and (7), the image S∘⇒+S \circ\Rightarrow_{+} as well as the inverse image ⇒−∘S\Rightarrow_{-} \circ S is always DD-saturated, regardless of S⊆Q×NS \subseteq Q \times\mathbb{N}.

For termination of our decision procedure it will be crucial that the semilinear sets it maintains form non-decreasing chains of DD-saturated sets X⊆Q×NX \subseteq Q \times\mathbb{N}, since we have:

Lemma 11. For every N>0N > 0, every non-decreasing chain of X1⊆X2⊆⋯X_1 \subseteq X_2 \subseteq\cdots of NN-saturated subsets of Q×NQ \times\mathbb{N} stabilizes.

Proof. The sequence MIN⁡(X1),MIN⁡(X2),…\operatorname{MIN}(X_1), \operatorname{MIN}(X_2),\ldots is a non-increasing chain of functions, ordered pointwise (assuming n<∞n < \infty for n∈Nn \in\mathbb{N}), and hence necessarily stabilizes due to well-foundedness of the function space Q×{0…N−1}→N∪{∞}Q \times\{0 \ldots N-1\} \to\mathbb{N} \cup\{\infty\}.

Before the proofs of Lemmas 6 and 7, a basic observation concerning individual segments:

Lemma 12. The relations ⇒0\Rightarrow_0, ⇒−\Rightarrow_-, ⇒+\Rightarrow_+ are effectively semilinear.

Proof. The reachability relation of the underlying 2-VASS V\mathcal{V} is effectively semilinear [2], which implies that so is ⇒\Rightarrow, 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 ⇒0\Rightarrow_0, ⇒−\Rightarrow_-, ⇒+\Rightarrow_+, each of them obtained by intersecting with a semilinear set, are also effectively semilinear.

Proof of Lemma 7. Recall that Φ3=(⇒−∘⇒0∗)∗\Phi_3 = (\Rightarrow_- \circ\Rightarrow_0^*)^*. By Lemmas 6 and 12, both the relations ⇒−\Rightarrow_- and ⇒0∗\Rightarrow_0^* are effectively semilinear. By a standard argument building upon [4 Thm. 6], the composed relation ⇒−∘⇒0∗\Rightarrow_- \circ\Rightarrow_0^* is also effectively semilinear, in particular meaning that the set (⇒−∘⇒0∗)∘S(\Rightarrow_- \circ\Rightarrow_0^*) \circ S is semilinear for every given semilinear set SS. Furthermore, as ⇒−\Rightarrow_- is source pumpable (7), and therefore the composed relation ⇒−∘⇒0∗\Rightarrow_- \circ\Rightarrow_0^* is so as well, the set (⇒−∘⇒0∗)∘S(\Rightarrow_- \circ\Rightarrow_0^*) \circ S is always DD-saturated.

In order to argue that the set Φ3∘{t}\Phi_3 \circ\{t\} is effectively semilinear we make use of Lemma 11, iterating the transformation

Xi+1:=Xi∪(⇒−∘⇒0∗)∘Xi,X_{i+1} := X_i \cup(\Rightarrow_- \circ\Rightarrow_0^*) \circ X_i,

starting from the initial set

X0:=(⇒−∘⇒0∗)∘{t},X_0 := (\Rightarrow_- \circ\Rightarrow_0^*) \circ\{t\},

until a fixpoint is reached. By the above observations, we deduce that both the initial set X0X_0, as well as every successive iterate Xi+1X_{i+1}, are effectively semilinear and DD-saturated; moreover it is self-evident that the sequence X0⊆X1⊆⋯X_0 \subseteq X_1 \subseteq\cdots is non-decreasing.

More explicitly, by Lemma 11 we have that at starting at some jj,

Xj=Xj+1=Xj+2=⋯X_j = X_{j+1} = X_{j+2} = \cdots

Since both the iteration Xi↦Xi+1X_i \mapsto X_{i+1} and the equality test Xi=Xi+1X_i = X_{i+1} are effective, the set

Φ3∘{t}={t}∪⋃i∈NXi={t}∪Xj\Phi_3 \circ\{t\} = \{t\} \cup\bigcup_{i \in\mathbb{N}} X_i = \{t\} \cup X_j

is effectively semilinear. We conclude the first part by noting that the proof is not specific to the starting set {t}\{t\}, and shows that Φ3∘T\Phi_3 \circ T is effectively semilinear given any semilinear T⊆Q×NT \subseteq Q \times\mathbb{N}, which will be useful in the second part.

Now we proceed to arguing that the set {s}∘Φ1\{s\} \circ\Phi_1 is effectively semilinear. To this aim we prefer to use another rational expression defining Φ1\Phi_1, where Φ3\Phi_3 appears as a subexpression:

Φ1=(⇒0∗∘Φ3∘⇒+)∗.\Phi_1 = (\Rightarrow_0^* \circ\Phi_3 \circ\Rightarrow_+)^*.

indeed, as in (4) in § 3, the inner subexpression ⇒0∗∘Φ3∘⇒+\Rightarrow_0^* \circ\Phi_3 \circ\Rightarrow_+ describes an arbitrary composition of segments of type ⇒0\Rightarrow_0 and ⇒−\Rightarrow_- that ends with one segment of type ⇒+\Rightarrow_+.

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:

X0:=f({s})Xi+1:=Xi∪f(Xi)X_0 := f(\{s\}) \qquad X_{i+1} := X_i \cup f(X_i)

where

f(S)=S∘(⇒0∗∘Φ3∘⇒+).f(S) = S \circ(\Rightarrow_0^* \circ\Phi_3 \circ\Rightarrow_+).

Similarly as before, knowing that ⇒+\Rightarrow_+ is target pumpable, we know that all XiX_i are DD-saturated sets, and therefore the sequence X0,X1,…X_0, X_1, \ldots stabilizes, and hence

{s}∘Φ1={s}∪Xj\{s\} \circ\Phi_1 = \{s\} \cup X_j

for some jj, similarly as before. The only missing ingredient is computability of the iteration Xi↦Xi+1X_i \mapsto X_{i+1}. However, in order to apply the previously shown computability of the function

T↦Φ3∘T(8)T \mapsto\Phi_3 \circ T \tag*{(8)}

which proceeds ’backward’, for computability of the function S↦f(S)S \mapsto f(S) which proceeds ’forward’, we need a trick. Note that the relation ⇒0∗∘Φ3∘⇒+\Rightarrow_0^* \circ\Phi_3 \circ\Rightarrow_+ is always target-pumpable since ⇒+\Rightarrow_+ is so by (6), and hence f(S)f(S) is always DD-saturated regardless of SS. To compute f(S)f(S), one first establishes, for every state q∈Qq \in Q, which remainders rr modulo DD appear in this set, by applying the transformation (8) to the set

(⇒+∘Xq,r),(9)(\Rightarrow_+ \circ X_{q,r}), \tag*{(9)}

where Xq,r={q(n)∣n≡rmod⁡D}X_{q,r} = \{q(n) \mid n \equiv r \mathbin{\operatorname{mod}} D\}, and checking nonemptiness of intersection with the set

S∘⇒0∗.(10)S \circ\Rightarrow_0^*. \tag*{(10)}

Both the sets (9), (10) are effectively semilinear due to Lemmas 6 and 12, and hence the set Φ3∘(⇒+∘Xq,r)\Phi_3 \circ(\Rightarrow_+ \circ X_{q,r}), and its intersection Yq,rY_{q,r} with (10), are computable. Knowing which remainders to expect, one then finds the precise representation min⁡(f(S))\min(f(S)) of f(S)f(S) by an exhaustive search. For every positively verified state-remainder pair (q,r)(q,r), namely one with Yq,r≠∅Y_{q,r} \ne\varnothing, one finds the least number nn such that q(n)∈f(S)q(n) \in f(S) and n≡rmod⁡Dn \equiv r \mathbin{\operatorname{mod}} D. For consecutive candidates k=0,1,…k = 0, 1, \ldots, apply the transformation (8) to the set

(⇒+∘{q(r+k⋅D)})(\Rightarrow_+ \circ\{q(r + k \cdot D)\})

and check nonemptiness of intersection with the set (10), until a nonempty intersection is found. This shows that the DD-saturated representation of f(S)f(S) may be computed, concluding the proof of the second part of Lemma 7.

Effective semilinearity of ⟹0∗\Longrightarrow_0^*: Proof of Lemma 6

In outline, we prove that Φ2=⟹0∗\Phi_2 = \Longrightarrow_0^* is essentially the reachability relation of an effectively constructible 1-CM M′\mathcal{M}', to which we apply Parikh’s theorem.

The key observation which makes the construction of M′\mathcal{M}' possible, is that the relation ⟹0\Longrightarrow_0 is essentially one-dimensional: for any pair of zero-testing control states q,q′∈Qq, q' \in Q and c∈{−C…C}c \in\{-C \ldots C\}, consider the set of pairs of initial and final counter values (n,n′)(n,n') such that n′=n+cn' = n + c and q(n)⟹0q′(n′)q(n) \Longrightarrow_0 q'(n'). We may describe this set in one dimension, defining

Xq,q′c={ n∣q(n)⟹0q′(n+c) }.(11)X^c_{q,q'} = \{\, n \mid q(n) \Longrightarrow_0 q'(n+c) \,\}. \tag*{(11)}

Since the values of nn and cc together determine n′n', the finite collection of sets Xq,q′cX^c_{q,q'} fully describes the ⟹0\Longrightarrow_0 relation.

Moreover, each set Xq,q′cX^c_{q,q'} is effectively semilinear, being the intersection of the effectively semilinear relation ⟹0\Longrightarrow_0 with the semilinear set {(q(n),q′(n′))∣n′=n+c}\{(q(n),q'(n')) \mid n' = n+c\}, projected down to one dimension. Hence, each Xq,q′cX^c_{q,q'} is ultimately periodic, with an effectively computable period Nq,q′cN^c_{q,q'} and threshold Mq,q′cM^c_{q,q'}. Define NN as the least common multiple of all the periods Nq,q′cN^c_{q,q'}, across all choices of cc, qq and q′q'.

Control states of M′\mathcal{M}'. Except for auxiliary states, to be clear from the construction below, the control states Q′Q' of M′\mathcal{M}' are the control states of M\mathcal{M} enriched with a number representing the remainder modulo NN of the current counter value:

Q′=Q×{0…N−1}∪(auxiliary states).Q' = Q \times\{0 \ldots N-1\} \cup\text{(auxiliary states)}.

We write q[r]q[r], instead of (q,r)(q,r), for the control state of M′\mathcal{M}' corresponding to q∈Qq \in Q and remainder r<Nr < N. As an invariant of our construction, counter values nn reachable in state q[r]q[r] in M′\mathcal{M}' always satisfy n≡rmod  Nn \equiv r \mod N.

The construction, to be detailed below, ensures the following correctness claim, for every pair q,q′∈Qq, q' \in Q of zero-testing control states and c∈{−C…C}c \in\{-C \ldots C\}:

q(n)⟹0q′(n+c) in M⟺q[r](n)⇢∗q′[r′](n+c) in M′,(12)q(n) \Longrightarrow_0 q'(n+c) \text{ in } \mathcal{M} \quad\Longleftrightarrow\quad q[r](n) \mathrel{\dashrightarrow^*} q'[r'](n+c) \text{ in } \mathcal{M}', \tag*{(12)}

where rr and r′r' are the remainders of nn and n+cn+c modulo NN, respectively, and ⇢∗\dashrightarrow^* denotes the subset of the reachability relation ⟶∗\longrightarrow^* of M′\mathcal{M}' where all the intermediate states are auxiliary.

In other words, when M′\mathcal{M}' is restricted to runs whose intermediate states are all auxiliary, it realizes the non-iterated relation ⟹0\Longrightarrow_0 of M\mathcal{M}. Once this restriction is lifted, M′\mathcal{M}' computes the iterated ⟹0∗\Longrightarrow_0^* relation.

Transitions of M′\mathcal{M}'. In control state q[r]q[r], the 1-CM M′\mathcal{M}' non-deterministically chooses a number c∈{−C…C}c \in\{-C \ldots C\}, and a next zero-testing state q′∈Qq' \in Q, such that the current counter value nn belongs to the set Xq,q′cX^c_{q,q'} as defined in (11). Upon positive test, M′\mathcal{M}' increments the counter by cc and goes to the next state q′[r+cmodN]q'[r+c \mathbin{\mathrm{mod}} N].

As the remainder of nn modulo Nq,q′cN^c_{q,q'} is fixed and determined by rr, checking membership n∈Xq,q′cn \in X^c_{q,q'} reduces to checking if n≥Mq,q′cn \geq M^c_{q,q'} (double by decrementing the counter by Mq,q′cM^c_{q,q'} and then incrementing it by Mq,q′cM^c_{q,q'} back) or checking if n=mn=m for some m<Mq,q′cm < M^c_{q,q'} (double similarly, by decrementing the counter by mm, a zero-test, and incrementing the counter by mm 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 ⟶∗\mathrel{\longrightarrow}^{*} of M′\mathcal{M}', for every zero-testing control states q,q′∈Qq,q' \in Q and n,n′∈Nn,n' \in\mathbb{N},

q(n)⟹0∗q′(n′) in M⟺q[r](n)⟶∗q′[r′](n′) in M′,(13)q(n) \mathrel{\Longrightarrow_{0}^{*}} q'(n') \text{ in } \mathcal{M} \quad\Longleftrightarrow\quad q[r](n) \mathrel{\longrightarrow^{*}} q'[r'](n') \text{ in } \mathcal{M}', \tag*{(13)}

where rr and r′r' are the remainders of nn and n′n' modulo NN, respectively. The construction of M′\mathcal{M}' 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 q,q′∈Qq,q' \in Q, we build a pushdown automaton recognizing the language

Lq,q′={anbn′∣q(n)⟹0∗q′(n′)},L_{q,q'} = \{ a^n b^{n'} \mid q(n) \mathrel{\Longrightarrow_{0}^{*}} q'(n') \},

or, equivalently,

{anbn′∣q[n mod N](n)⟶M′∗q′[n′ mod N](n′)}.\{ a^n b^{n'} \mid q[n \bmod N](n) \mathrel{\longrightarrow_{\mathcal{M}'}^{*}} q'[n' \bmod N](n') \}.

Applying Parikh’s Theorem to this language, we’ll get that the relation ⟹0∗\mathrel{\Longrightarrow_{0}^{*}} 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 M′\mathcal{M}' to a labelled 1-CM, where every transition is labelled with a symbol from the alphabet {a,b}\{a,b\}, or with ε\varepsilon. Fix a pair of zero-testing states q,q′∈Qq,q' \in Q for which Lq,q′L_{q,q'} is to be recognized. Take all the transitions of M′\mathcal{M}' as unlabelled (labelled with ε\varepsilon), add NN extra states p[0]…p[N−1]p[0]\ldots p[N-1] forming an aa-labelled cycle of transitions incrementing the counter by 1:

Construction of the labelled 1-CM $\mathcal{M}'$

Figure 3. The construction we use to extract the language Lq,q′L_{q,q'} out of the 1-CM M′\mathcal{M}'.

(p[i],update(1),p[i+1 mod N])for all i∈{0…N−1}(p[i],\mathbf{update}(1),p[i+1 \bmod N]) \qquad\text{for all } i \in\{0\ldots N-1\}

(which assures storing the remainder modulo NN in states), add another NN extra states p′[N−1]…p′[0]p'[N-1]\ldots p'[0] forming a bb-labelled cycle of transitions decrementing the counter by 1:

(p′[i],update(−1),p′[i−1 mod N])for all i∈{0…N−1},(p'[i],\mathbf{update}(-1),p'[i-1 \bmod N]) \qquad\text{for all } i \in\{0\ldots N-1\},

and finally add 0-update transitions from p[i]p[i] to q[i]q[i], and from q′[i]q'[i] to p′[i]p'[i]:

(p[i],update⁡(0),q[i]),(q′[i],update⁡(0),p′[i])for all i∈{0…N−1}.(p[i],\operatorname{update}(0),q[i]),\quad(q'[i],\operatorname{update}(0),p'[i]) \quad\text{for all } i \in\{0\ldots N-1\}.

A labelled 1-CM extended in this manner recognizes the language Lq,q′L_{q,q'} when considered with initial configuration p[0](0)p[0](0) and final configuration p′[0](0)p'[0](0). By the previous discussion, the lemma follows by Parikh’s theorem.

Target pumping: Proof of Lemma 9

We focus on proving point (2→2)(2\to2), noticing however that literally the same argument works for point (1→2)(1\to2). The other two points, namely (2→1)(2\to1) and (1→1)(1\to1), follow immediately by swapping the coordinates.

To ease the presentation, we introduce the following definitions:

  • For a transition t=(q,update⁡(w),q′)∈Tt=(q,\operatorname{update}(w),q')\in T, the states q,q′q,q' are said to be the source and target of tt respectively, and the vector ww is said to be the effect of tt.

  • 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 ρ\rho is said to be fireable at a configuration q(v)q(\mathbf{v}) if there exists a configuration q′(v′)q'(\mathbf{v}') such that q(v)→ρq′(v′)q(\mathbf{v}) \xrightarrow{\rho} q'(\mathbf{v}'). This amounts to requiring that ρ\rho can be executed starting from q(v)q(\mathbf{v}), without the counters having to go negative along the way. We denote the target configuration q′(v′)q'(\mathbf{v}') thus obtained by q(v);ρq(\mathbf{v});\rho.

  • For paths ρ1\rho_1 and ρ2\rho_2, denote their concatenation by ρ1;ρ2\rho_1;\rho_2.

  • For a path ρ\rho, the transposed path ρˉ\bar{\rho} is obtained by applying the symmetry assumption at each transition. If ρ\rho has effect (a,b)(a,b), ρˉ\bar{\rho} has effect (b,a)(b,a).

We define the norm of a vector w=(w1,w2)∈Z2\mathbf{w}=(w_1,w_2)\in\mathbb{Z}^2 to be the maximal absolute value of its components, ∥w∥=max⁡{∣w1∣,∣w2∣}\lVert\mathbf{w}\rVert=\max\{|w_1|,|w_2|\}, and the norm of a 2-vass V=(Q,T)\mathcal{V}=(Q,T) to be the maximal norm of the effects of its transitions, ∥V∥=max⁡{∥w∥∣(q,update⁡(w),q′)∈T}\lVert\mathcal{V}\rVert=\max\{\lVert\mathbf{w}\rVert\mid(q,\operatorname{update}(\mathbf{w}),q')\in T\}.

Proof of Lemma 9 (2→2)(2\to2). Consider a fixed symmetric 2-vass V=(Q,T)\mathcal{V}=(Q,T) and a run σ:q(0,a)→∗q′(0,a′)\sigma:q(0,a)\xrightarrow{*}q'(0,a') for some a,a′∈Na,a'\in\mathbb{N}. Assuming that the difference a′−aa'-a is sufficiently large (namely larger than some CC, depending only on V\mathcal{V}), we modify the run to lift the target configuration to q′(0,a′+γDσ)q'(0,a'+\gamma D_\sigma) for any γ∈N\gamma\in\mathbb{N} and some particular DσD_\sigma, which depends on both V\mathcal{V} and σ\sigma. Holding V\mathcal{V} fixed, DσD_\sigma will only attain finitely many different values, hence we argue that taking the least common multiple of all DσD_\sigma yields a constant DD satisfying the claim of the lemma.

Denote by σ~\tilde{\sigma} the sequence of transitions fired along the run σ\sigma, obtaining its corresponding path. According to the linear-path-scheme (LPS) decomposition of [2 Thm. 1], we may assume w.l.o.g. that σ~\tilde{\sigma} is built of paths t0,…,tℓt_0,\ldots,t_\ell and cycles c1,…,cℓc_1,\ldots,c_\ell:

σ~∈t0 c1∗ t1 c2∗ ⋯ cℓ∗ tℓ,(14)\tilde{\sigma}\in t_0\,c_1^*\,t_1\,c_2^*\,\cdots\,c_\ell^*\,t_\ell, \tag*{(14)}

where the lengths of each path tit_i and cycle cjc_j are at most ee, and both ℓ\ell and ee are bounded by a polynomial of the the size ∣V∣=∣Q∣+2⋅∥V∥⋅∣T∣|\mathcal{V}|=|Q|+2\cdot\lVert\mathcal{V}\rVert\cdot|T| of the unary representation of V\mathcal{V}. Note that we do not claim any bound the number njn_j of iterations in σ~\tilde{\sigma} of the cycles cjc_j. Let C0≤e∥V∥C_0 \le e\lVert\mathcal{V}\rVert be the minimal value such that every cycle of V\mathcal{V} of length at most ee is fireable at v0=(C0,C0)v_0 = (C_0,C_0). Call a cycle cjc_j major if its number of iterations njn_j is larger than 2C02C_0, and minor otherwise. W.l.o.g. we may assume that all cycles are major, by inlining any minor cycles cic_i into their neighboring one-off paths ti−1t_{i-1} and tit_i. After this operation, the lengths of the one-off paths are bounded by e′:=e(2C0ℓ+ℓ+1)e' := e(2C_0\ell+\ell+1).

Call a cycle cjc_j sum-increasing if its effect (xj,yj)(x_j,y_j) satisfies xj+yj>0x_j+y_j>0. We claim that, by setting a large enough value of CC, we can guarantee that the run will contain at least one (major) sum-increasing cycle. Indeed, as we are assuming that a′−a>Ca'-a>C, the sum of counters must increase by more than CC along σ\sigma. Thus, it is enough when

C≥C1:=2∥V∥emax⁡′(ℓmax⁡+1),C \ge C_1 := 2\lVert\mathcal{V}\rVert e'_{\max}(\ell_{\max}+1),

where emax⁡′e'_{\max} and ℓmax⁡\ell_{\max} are the (polynomial in ∥V∥\lVert\mathcal{V}\rVert) bounds on e′e' and ℓ\ell, 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 (0,+)(0,+), horizontal (+,0)(+,0), or one of (+,−)(+,-), (+,+)(+,+), or (−,+)(-,+). We classify these into three cases (Figure 4, left).

Effects of individual cycles and proof strategy for Case 2

Figure 4. A view of the (Δx,Δy)(\Delta x,\Delta y) 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 cjc_j, we make use of the symmetry assumption to obtain the transposed cycle cj‾\overline{c_j}. The shaded area demarcates the effects we can obtain from linear combinations of cjc_j and cj‾\overline{c_j} with positive coefficients. Observe that the shaded area contains the desired vertical effect (green, not to scale).

Case 1: Some sum-increasing cycle cjc_j has vertical (0,+)(0,+) effect. One extra iteration of this cycle yields the claim, with the vertical effect of the cycle determining DσD_\sigma.

Case 2: Some sum-increasing cycle cjc_j has effect (−,+)(-,+) or (+,−)(+,-). Assume that cjc_j has effect (−x,y)(-x,y) for some positive integers x,yx,y. Observe that y>xy>x. The case of (+,−)(+,-) effect is analogous.

As an outline, we will seek to increase the iteration count njn_j of the cycle cjc_j, and introduce into the run the transposed cycle cj‾\overline{c_j}, such that the net effect of our modifications becomes vertical (see Figure 4, right).

For our argument it is enough if the njn_j is large enough to guarantee that somewhere in the middle of cjnjc_j^{n_j}, the transposed cycle cj‾\overline{c_j} becomes fireable. We observe the following key claim, relying on the fact that the effect of cjc_j is nonzero on both coordinates (in particular note that we do not use the sum-increasing assumption for this claim):

Claim 13. If cjnjc_j^{n_j} is fireable at q(v)q(\mathbf{v}), then for any repetition count ii satisfying C0≤i≤nj−C0C_0 \le i \le n_j-C_0, the transposed cycle cˉj\bar{c}_j is fireable at q(v)q(\mathbf{v}); cˉj\bar{c}_j.

Proof. The nj+1n_j+1 configurations at the boundaries between the iterations of cjc_j within cjnjc_j^{n_j} form an arithmetic progression given by (xi,yi)=(x0−ix,y0+iy)(x_i,y_i)=(x_0-ix,y_0+iy). Observe that for C0≤i≤nj−C0C_0 \le i \le n_j-C_0 we have

yi=y0+iy≥y0+i≥C0,y_i = y_0+iy \ge y_0+i \ge C_0,
xi=x0−ix=xnj+(nj−i)x≥xnj+nj−i≥C0.x_i = x_0-ix = x_{n_j}+(n_j-i)x \ge x_{n_j}+n_j-i \ge C_0.

Recall now that, having eliminated all minor cycles by inlining, we must have nj>2C0n_j>2C_0. Thus, the range of values of ii admissible for Claim 13 is non-empty. Setting i:=C0+1i:=C_0+1, we have that the transposed cycle cˉj\bar{c}_j is fireable after the first C0+1C_0+1 iterations of cjc_j within σ\sigma. Equivalently, shifting the point of view one iteration earlier, the concatenation cj;cˉjc_j;\bar{c}_j is fireable after cjC0c_j^{C_0}.

Recall we have that y>xy>x, as the cycle is sum-increasing. Thus, the effect of cj;cˉjc_j;\bar{c}_j, being (y−x,y−x)(y-x,y-x), is positive on both coordinates, and cj;cˉjc_j;\bar{c}_j may be fired arbitrarily many times in the middle of cjnjc_j^{n_j}, without interference with the remainder of σ\sigma.

Now set u:=x(y−x)u:=x(y-x). By iterating xx times the cycle cj;cˉjc_j;\bar{c}_j, we get a cycle with effect (u,u)(u,u), and then appending cˉjy−x\bar{c}_j^{y-x} we get the desired vertical effect. Indeed, the effect of

(cj;cˉj)x;cˉjy−x(c_j;\bar{c}_j)^x;\bar{c}_j^{y-x}

is (0,(x+y)(y−x))(0,(x+y)(y-x)), and this cycle is still fireable in the middle of cjnjc_j^{n_j}. We thus get the claim with Dσ=(x+y)(y−x)D_\sigma=(x+y)(y-x).

Case 3: All sum-increasing cycles have (+,0)(+,0) or (+,+)(+,+) effect. Let us restrict our attention to those cycles cjc_j, whose effect (xj,yj)(x_j,y_j) satisfies xj≠0x_j \ne0. Depending on whether xj>0x_j > 0 or xj<0x_j < 0, we call such cycles horizontally positive, or horizontally negative respectively. Define the steepness of such cycles cjc_j as yj/xjy_j/x_j, and denote it by φj\varphi_j. 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).

The steepness comparison central to the proof strategy of Case 3

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 c1c_1, c2c_2, and c3c_3, where c2c_2 is horizontally positive, and the other two are horizontally negative. The cycle c1c_1 is steeper than c2c_2, and c2c_2 is steeper than c3c_3. 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 cic_i, with three candidates for a subsequent horizontally-negative cycle cjc_j (cf. Claim 14), illustrated in terms of their combined effect. Observe how the vertical effect obtained this way is positive exactly when cic_i is steeper than cjc_j.

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 i<ji < j such that cic_i is a sum-increasing cycle, cjc_j is horizontally negative, and cic_i is steeper than cjc_j (i.e. φi>φj\varphi_i > \varphi_j).

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.

A run prefix in the counter configuration space

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 (0,a′)(0,a'), above both invariant lines.

For a cycle cic_i, denote by βi\beta_i the steepness of the most recent record-breaking cycle, i.e.

βi={max⁡(βi−1,φi)if ci sum-increasingβi−1otherwise\beta_i = \begin{cases} \max(\beta_{i-1},\varphi_i) & \text{if } c_i\text{ sum-increasing}\\ \beta_{i-1} & \text{otherwise} \end{cases}

with β0=0\beta_0 = 0 as the initial value. As one would expect, the value of βi\beta_i will define the slope of each line. Concretely specifying the yy-intercept, however, requires a bit more work.

Define (Xipre,Yipre)(X_i^{\mathrm{pre}},Y_i^{\mathrm{pre}}) and (Xipost,Yipost)(X_i^{\mathrm{post}},Y_i^{\mathrm{post}}) to be the counter values the run achieves immediately before and after cinic_i^{n_i}, respectively. Let kk be the index of the first sum-increasing cycle of the run. For i≥ki \ge k, define Si≤C1S_i \le C_1 as the sum of the norms of the effects of all one-off paths between ckc_k and cic_i, i.e. writing ∥t∥\lVert t\rVert for the sum of norms of transitions along a path tt,

Si=∑j=ki−1∥tj∥S_i = \sum_{j=k}^{i-1} \lVert t_j\rVert

We extend the definitions in a natural way to i=ℓ+1i = \ell+ 1 where relevant: let (Xℓ+1pre,Yℓ+1pre)(X_{\ell+1}^{\mathrm{pre}}, Y_{\ell+1}^{\mathrm{pre}}) be the counter values of the run’s target configuration, and denote by Sℓ+1S_{\ell+1} the sum of norms of effects of all one-off paths after ckc_k, up to and including tℓt_\ell.

By induction on i≥ki \ge k, we will now prove that the pair (Xipre,Yipre)(X_i^{\mathrm{pre}}, Y_i^{\mathrm{pre}}) of counter values will always satisfy

Yipre≤Ykpre+Si(1+βi)+βiXipre.(15)Y_i^{\mathrm{pre}} \le Y_k^{\mathrm{pre}} + S_i(1+\beta_i) + \beta_i X_i^{\mathrm{pre}} . \tag*{(15)}

Geometrically, this defines the dashed lines in Figure 6.

At i=ki = k, the inequality trivially holds. Suppose then that the inequality holds at a specific i≥ki \ge k, aiming to prove it for i+1i + 1.

We shall follow the structure of the run, aiming first to prove that after executing the effect of cic_i, the configuration (Xipost,Yipost)(X_i^{\mathrm{post}}, Y_i^{\mathrm{post}}) stays below the same line, i.e.

Yipost≤Ykpre+Si(1+βi)+βiXipost.(16)Y_i^{\mathrm{post}} \le Y_k^{\mathrm{pre}} + S_i(1+\beta_i) + \beta_i X_i^{\mathrm{post}} . \tag*{(16)}

See Figure 7 (left) for an illustration of this step. Symbolically, writing Xipost=Xipre+nixiX_i^{\mathrm{post}} = X_i^{\mathrm{pre}} + n_i x_i and Yipost=Yipre+niyiY_i^{\mathrm{post}} = Y_i^{\mathrm{pre}} + n_i y_i, we see that our aim is to prove yi≤βixiy_i \le\beta_i x_i. The first case, easily handled, is when xi=0x_i = 0. Indeed, we handle cycles of vertical effect (0,+)(0, +) in Case 1, so if we encounter such a cycle here, then yi≤0y_i \le0 must hold.

Three geometric diagrams illustrating the invariant line

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 x≥0x \ge0, we may freely make the invariant line steeper as long as the yy-intercept doesn’t get lowered in the process.

In the interesting case where xi≠0x_i \ne0, we apply the definition of φi\varphi_i to express the desired inequality as φixi≤βixi\varphi_i x_i \le\beta_i x_i, and consider the sign of xix_i. For a horizontally positive cycle, i.e. xi>0x_i > 0, we need φi≤βi\varphi_i \le\beta_i. If cic_i is sum-increasing, this holds by definition; otherwise note φi≤0≤βi\varphi_i \le0 \le\beta_i.

Finally, let cic_i be a horizontally negative cycle. In that situation, we need φi≥βi\varphi_i \ge\beta_i. Let jj be the most recent record-breaking cycle before ii, which must exist, as i≥ki \ge k (and i=ki = k is ruled out by cic_i being horizontally negative). Now note that if we had φi<βi=φj\varphi_i < \beta_i = \varphi_j, cycles cjc_j and cic_i would satisfy Claim 14. As we are assuming that the claim doesn’t hold, we indeed have φi≥βi\varphi_i \ge\beta_i, thereby establishing (16).

Our next focus shall be handling the effect of tit_i (Figure 7, center), proving that

Yi+1pre≤Ykpre+Si+1(1+βi)+βiXi+1pre.(17)Y_{i+1}^{\mathrm{pre}} \le Y_k^{\mathrm{pre}} + S_{i+1}(1+\beta_i) + \beta_i X_{i+1}^{\mathrm{pre}} . \tag*{(17)}

With (Δx,Δy)(\Delta x, \Delta y) denoting the effect of the one-off path tit_i, we have Xi+1pre=Xipost+ΔxX_{i+1}^{\mathrm{pre}} = X_i^{\mathrm{post}} + \Delta x, and analogously, Yi+1pre=Yipost+ΔyY_{i+1}^{\mathrm{pre}} = Y_i^{\mathrm{post}} + \Delta y. Comparing with (16), we see that it’ll suffice to show

Δy≤∥ti∥(1+βi)+βiΔx\Delta y \le\lVert t_i\rVert(1+\beta_i) + \beta_i\Delta x

(recall that Si+1=Si+∥ti∥S_{i+1}=S_i+\lVert t_i\rVert). As both ∣Δx∣\lvert\Delta x\rvert and ∣Δy∣\lvert\Delta y\rvert are bounded by ∥ti∥\lVert t_i\rVert, we have

Δy≤∥ti∥,\Delta y \le\lVert t_i\rVert,
−Δx≤∥ti∥.-\Delta x \le\lVert t_i\rVert.

Multiplying the latter by βi\beta_i and adding the two inequalities together, we obtain

Δy−βiΔx≤∥ti∥(1+βi),\Delta y-\beta_i\Delta x \le\lVert t_i\rVert(1+\beta_i),

as required.

Having now established (17), it remains to raise the slope of the invariant line to βi+1\beta_{i+1} (compare Figure 7, right). We note that βi≤βi+1\beta_i\le\beta_{i+1}, and moreover both Si+1S_{i+1} and Xi+1preX_{i+1}^{\mathrm{pre}} are nonnegative, so we have

Yi+1pre≤Ykpre+Si+1(1+βi)+βiXi+1pre≤Ykpre+Si+1(1+βi+1)+βi+1Xi+1pre.Y_{i+1}^{\mathrm{pre}}\le Y_k^{\mathrm{pre}}+S_{i+1}(1+\beta_i)+\beta_iX_{i+1}^{\mathrm{pre}} \le Y_k^{\mathrm{pre}}+S_{i+1}(1+\beta_{i+1})+\beta_{i+1}X_{i+1}^{\mathrm{pre}}.

This ends the induction, and so we get (15) up to and including i=ℓ+1i=\ell+1. As (Xℓ+1pre,Yℓ+1pre)=(0,a′)(X_{\ell+1}^{\mathrm{pre}},Y_{\ell+1}^{\mathrm{pre}})=(0,a') is the final configuration, we have:

a′≤Ykpre+Sℓ+1(1+βℓ+1).a'\le Y_k^{\mathrm{pre}}+S_{\ell+1}(1+\beta_{\ell+1}).

Let us now focus on establishing an upper bound for each expression occurring on the right-hand side. Firstly, we have Sℓ+1≤C1S_{\ell+1}\le C_1, which should be clear from the definition of the latter. Next, note that for any cycle cic_i we have φi=yi/xi≤∣yi∣≤e′∥V∥\varphi_i=y_i/x_i\le\lvert y_i\rvert\le e'\lVert V\rVert, and therefore βℓ+1≤e′∥V∥\beta_{\ell+1}\le e'\lVert V\rVert.

Finally, for YkpreY_k^{\mathrm{pre}}, we note that Ykpre≤Xkpre+YkpreY_k^{\mathrm{pre}}\le X_k^{\mathrm{pre}}+Y_k^{\mathrm{pre}}, and analyze the latter instead. Recall that (Xkpre,Ykpre)(X_k^{\mathrm{pre}},Y_k^{\mathrm{pre}}) are the counter values immediately before the first sum-increasing cycle of the run, so any increase above the initial counter sum of aa is fully attributable to the effects of the one-off paths before ckc_k. Thus, we get Ykpre≤a+C1Y_k^{\mathrm{pre}}\le a+C_1. In summary, we obtain

a′≤a+C1+C1(1+e′∥V∥)=a+C1(2+e′∥V∥).a'\le a+C_1+C_1(1+e'\lVert V\rVert)=a+C_1(2+e'\lVert V\rVert).

As the assumption of the lemma is that a′−a>Ca'-a>C, we can obtain a contradiction by setting

C:=C1(2+emax⁡′∥V∥).C:=C_1(2+e'_{\max}\lVert V\rVert).

Take any cycles ci,cjc_i,c_j, where i<ji<j, as given by Claim 14. Their horizontal effects satisfy xi>0x_i>0 and xj<0x_j<0, and hence the sum of the effects of ci−xjc_i^{-x_j} and cjxic_j^{x_i} is vertical and equal (0,h)(0,h) for h=−xjyi+xiyj>0h=-x_jy_i+x_iy_j>0. Expanding cinic_i^{n_i} with ci−xjc_i^{-x_j} and cjnjc_j^{n_j} with cjxic_j^{x_i} yields a run ending in q′(0,a′+Dσ)q'(0,a'+D_\sigma), where Dσ=hD_\sigma=h. Moreover, this modification will never decrease any intermediate value of the counters, as compared to the original run σ\sigma. The proof of Case 3 is thus completed.

To summarize, in all the three cases the sufficiently large value of CC is C:=C1(2+emax⁡′∥V∥)C:=C_1(2+e'_{\max}\lVert V\rVert). The proof of Lemma 9 is thus completed.

Undecidability for Z3-cms

We now turn to Z3\mathbb{Z}_3-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 (n−1)(n-1)-CMs to Zn\mathbb{Z}_n-CMs, showing that reachability is undecidable in Zn\mathbb{Z}_n-CMs, for n≥3n\ge3. For concreteness, however, we focus on the case of $n=3.

Proof of Theorem 2. Recall that a Z3\mathbb{Z}_3-CM is a 3-CM such that for any transition labeled by update⁡(x,y,z)\operatorname{update}(x,y,z), the transitions update⁡(y,z,x)\operatorname{update}(y,z,x) and update⁡(z,x,y)\operatorname{update}(z,x,y) are also present between the same pair of states. Note however, that the Z3\mathbb{Z}_3-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 M=(Q,T)\mathcal{M}=(Q,T), we shall construct a Z3\mathbb{Z}_3-CM M′=(Q′,T′)\mathcal{M}'=(Q',T') that simulates it, where Q′Q' is a copy of QQ with auxiliary states adjoined.

For a configuration q(a,b)q(a,b) of M\mathcal{M}, the corresponding configuration of M′\mathcal{M}' shall have the form q(3a+2,3b+2,0)q(3a+2,3b+2,0), with two main counters keeping track of the values of the counters of M\mathcal{M}, 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 (q,update⁡(x,y),q′)∈T(q,\operatorname{update}(x,y),q')\in T, we include in T′T' the transitions in use by the following fragment of a run:

q(3a+2, 3b+2, 0)→update⁡(3x−1,3y−1,0)(3(a+x)+1, 3(b+y)+1, 0)→zero-test⁡(∗)(3(a+x)+1, 3(b+y)+1, 0)→update⁡(1,1,0)(3(a+x)+2, 3(b+y)+2, 0)→zero-test⁡(∗)q′(3(a+x)+2, 3(b+y)+2, 0).\begin{aligned} q(3a+2,\ 3b+2,\ 0) &\xrightarrow{\operatorname{update}(3x-1,3y-1,0)} (3(a+x)+1,\ 3(b+y)+1,\ 0) \\ &\xrightarrow{\operatorname{zero-test}(*)} (3(a+x)+1,\ 3(b+y)+1,\ 0) \\ &\xrightarrow{\operatorname{update}(1,1,0)} (3(a+x)+2,\ 3(b+y)+2,\ 0) \\ &\xrightarrow{\operatorname{zero-test}(*)} q'(3(a+x)+2,\ 3(b+y)+2,\ 0). \end{aligned}

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 update⁡(3x−1,3y−1,0)\operatorname{update}(3x-1,3y-1,0) 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 update⁡(1,1,0)\operatorname{update}(1,1,0) 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 M\mathcal{M}. 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 (q,zero-test⁡(1),q′)∈T(q,\operatorname{zero-test}(1),q')\in T of M\mathcal{M}, M′\mathcal{M}' performs the following steps:

q(3a+2, 3b+2, 0)→update⁡(−2,−1,+2)(3a, 3b+1, 2)→zero-test⁡(∗)(0, 3b+1, 2)→update⁡(+2,+1,−2)(2, 3b+2, 0)→zero-test⁡(∗)q′(2, 3b+2, 0).\begin{aligned} q(3a+2,\ 3b+2,\ 0) &\xrightarrow{\operatorname{update}(-2,-1,+2)} (3a,\ 3b+1,\ 2) \\ &\xrightarrow{\operatorname{zero-test}(*)} (0,\ 3b+1,\ 2) \\ &\xrightarrow{\operatorname{update}(+2,+1,-2)} (2,\ 3b+2,\ 0) \\ &\xrightarrow{\operatorname{zero-test}(*)} q'(2,\ 3b+2,\ 0). \end{aligned}

As the instruction update(−2,−1,+2)(-2,-1,+2) 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 (0,1,2)(0,1,2) mod 3 respectively, this zero-test will only succeed when 3a=03a=0, exactly as required to simulate a zero-test(1)(1) instruction.

To finish simulating the zero-test, update(+2,+1,−2)(+2,+1,-2) 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 −2-2, 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 −2-2 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 (q,update(w),q′)(q,\mathbf{update}(\mathbf{w}),q') are single-counter, that is w\mathbf{w} 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 q(v1,v2)q(v_1,v_2) of a symmetric 2-CM would be simulated by q(2v1,2v2+1)q(2v_1,2v_2+1), thus doubling the counter values and distinguishing them by parity. Consequently, a transition (q,update(w1,w2),q′)(q,\mathbf{update}(w_1,w_2),q') is simulated a transition (q,update(2w1,2w2),q′)(q,\mathbf{update}(2w_1,2w_2),q'). Therefore the update transitions, even symmetric ones, preserve parity of both counters. Due to parity distinction, a transition (q,zero−test(∗),q′)(q,\mathbf{zero-test}(*),q') checking if an unspecified counter is 0, in fact checks if counter 1 is 0. On the other hand, simulation of transition (q,zero−test(2),q′)(q,\mathbf{zero-test}(2),q') is done in three steps, using two auxiliary intermediate states pt,pt′p_t,p'_t:

(q,update(1,−1),pt)(pt,zero−test(∗),pt′)(pt′,update(−1,1),q′).(18)(q,\mathbf{update}(1,-1),p_t)\qquad(p_t,\mathbf{zero-test}(*),p'_t)\qquad(p'_t,\mathbf{update}(-1,1),q'). \tag*{(18)}

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 GG-CMs, for an arbitrary number d>2d>2 of counters, and arbitrary permutation group G≤SdG\leq S_d. To this aim we distinguish between the counters by remainders modulo dd, simulate a configuration q(a1,…,ad)q(a_1,\ldots,a_d) by

q(da1,da2+1,…,dad+d−1),q(da_1,da_2+1,\ldots,da_d+d-1),

and simulate a transition (q,update(v),q′)(q,\mathbf{update}(\mathbf{v}),q') by (q,update(dv),q′)(q,\mathbf{update}(d\mathbf{v}),q'). Furthermore, to correctly simulate a zero-test of counter j+1>1j+1>1, say a transition (q,zero−test(j+1),q′)(q,\mathbf{zero-test}(j+1),q'), we replace the vectors (1,−1)(1,-1) and (−1,1)(-1,1) in the first and last transition in (18) by

(j,…,j,−j,j,…,j)and(−j,…,−j,j,−j,…,−j),(j,\ldots,j,-j,j,\ldots,j)\qquad\text{and}\qquad(-j,\ldots,-j,j,-j,\ldots,-j),

respectively, where the unique value of negative (left) or positive (right) sign appears on the (j+1)(j+1)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 dd-cms, d≥2d \ge2, 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 q(0,…,0)⟶∗q′(0,…,0)q(0,\ldots,0) \longrightarrow^{*} q'(0,\ldots,0), 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 M=(Q,T)\mathcal{M}=(Q,T), the source s=q(w)s=q(\mathbf{w}) and the target t=q′(w′)t=q'(\mathbf{w}'), namely

n=∣Q∣+∣Tzero−test∣+2⋅∥V∥⋅∣Tupdate∣+∥w∥+∥w′∥,n=|Q|+|T_{\mathrm{zero-test}}|+2\cdot\lVert\mathcal{V}\rVert\cdot|T_{\mathrm{update}}|+\lVert\mathbf{w}\rVert+\lVert\mathbf{w}'\rVert,

where Tzero−testT_{\mathrm{zero-test}} and TupdateT_{\mathrm{update}} are the sets of zero-test and update transitions of M\mathcal{M}, respectively, and V=(Q,Tupdate)\mathcal{V}=(Q,T_{\mathrm{update}}) is the underlying 2-vass. Our objective is to provide an elementary upper bound in terms of nn, 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 CC and DD. The constant

C:=C1(2+emax⁡∥V∥),whereC1=2∥V∥emax⁡′(ℓmax⁡+1),C:=C_{1}(2+e_{\max}\lVert\mathcal{V}\rVert), \qquad\text{where}\qquad C_{1}=2\lVert\mathcal{V}\rVert e_{\max}^{\prime}(\ell_{\max}+1),

is polynomial in nn. The norm of the effect of every cycle of length at most emax⁡e_{\max} is bounded by emax⁡∥V∥e_{\max}\lVert\mathcal{V}\rVert, where emax⁡e_{\max} is the maximal length ee (polynomial in nn), and hence all values DσD_{\sigma} appearing in all the three cases in the proof of Lemma 9 are bounded by 2(emax⁡∥V∥)22(e_{\max}\lVert\mathcal{V}\rVert)^2, thus polynomially in nn. Taking as DD the least common multiple of all DσD_{\sigma} is enough for the claim of the lemma. In summary:

Claim 15. The constants CC and DD of Lemma 9 are bounded polynomially and exponentially in nn, respectively.

Terminology. We use the kk-exponential function exp⁡k\operatorname{exp}_{k}, defined as exp⁡0(m)=m\operatorname{exp}_{0}(m)=m, and exp⁡k+1(m)=2exp⁡k(m)\operatorname{exp}_{k+1}(m)=2^{\operatorname{exp}_{k}(m)}. Whenever a base-period representation of a semilinear set XX is clear from the context, we write ∥X∥\lVert X\rVert for the maximum of norms of bases and periods of this representation. In the sequel we say that a semilinear set XX is kk-exponentially semilinear if given M\mathcal{M}, one can compute a base-period representation of XX of norm bounded by ∥X∥≤exp⁡k(poly⁡(n))\lVert X\rVert\le\operatorname{exp}_{k}(\operatorname{poly}(n)).

Bounds for Lemma 12. According to the linear-path-scheme decomposition of [2 Thm. 1], whenever a configuration tt is reachable from ss in the underlying 2-vass V\mathcal{V} of M\mathcal{M}, tt is also reachable from ss by a run

σ∈t0 c1∗ t1 c2∗⋯cℓ∗ tℓ,(19)\sigma\in t_{0}\,c_{1}^{*}\,t_{1}\,c_{2}^{*}\cdots c_{\ell}^{*}\,t_{\ell}, \tag*{(19)}

where ℓ\ell is polynomial in nn, and t0,…,tℓt_{0},\ldots,t_{\ell} are paths and c1,…,cℓc_{1},\ldots,c_{\ell} are cycles of length polynomial in nn ((14)). As shown in [2], once ℓ\ell, t0,…,tℓt_{0},\ldots,t_{\ell} and c1,…,cℓc_{1},\ldots,c_{\ell} are fixed, the reachability relation along all runs of the form (19) is the union of (the projections of) the solution sets of instances II of the integer linear programming problem of size polynomial in nn, and hence effectively semilinear. Moreover, numbers appearing in II are bounded exponentially in nn, 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 nn. Summing over all choices of ℓ\ell, t0,…,tℓt_0,\ldots,t_\ell and c1,…,cℓc_1,\ldots,c_\ell, we conclude that the reachability relation ⟶∗\longrightarrow^* of V\mathcal{V} is exponentially semilinear. The same applies to the relation ⇒⊆(Q×N)2\Rightarrow\subseteq(Q \times\mathbb{N})^2, which is essentially the intersection of ⟶∗\longrightarrow^* with a linear set fixing some coordinates to 0. Finally, we transfer the same effective bounds to the three subrelations ⇒0,⇒+,⇒−\Rightarrow_0,\Rightarrow_+,\Rightarrow_- by noticing that each of them is the intersection of ⇒\Rightarrow with a semilinear set whose bases and periods are of norm at most C+1C+1, the constant of Lemma 9 (which is polynomial in nn), 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 r1,r2⊆(Q×N)2r_1,r_2 \subseteq(Q \times\mathbb{N})^2 satisfy ∥r1∩r2∥≤(O(1)+∥r1∥⋅∥r2∥)O(1)\lVert r_1 \cap r_2\rVert\leq(O(1)+\lVert r_1\rVert\cdot\lVert r_2\rVert)^{O(1)}.

We have thus shown:

Claim 17. The relations ⇒0,⇒+,⇒−\Rightarrow_0,\Rightarrow_+,\Rightarrow_- are exponentially semilinear.

Bound for Lemma 6. By the above effective exponential bounds on bases and periods of ⇒0\Rightarrow_0, we conclude that sets Xq,q′cX^{c}_{q,q'} (11) in the proof of Lemma 6 have base-period representations with at most exponential periods and bases. The period Nq,q′cN^{c}_{q,q'} and threshold Mq,q′cM^{c}_{q,q'} of ultimately periodic presentation of Xq,q′cX^{c}_{q,q'} 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 NN of all periods of Nq,q′cN^{c}_{q,q'}, across all choices of cc, qq and q′q', which is doubly exponential. In consequence, the 1-cm M′\mathcal{M}' 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 ⇒0∗\Rightarrow^*_0. As both construction of M′\mathcal{M}' and Parikh’s theorem are effective, we have thus shown:

Claim 18. The relation ⇒0∗\Rightarrow^*_0 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 r1,r2⊆(Q×N)2r_1,r_2 \subseteq(Q \times\mathbb{N})^2 satisfy ∥r1∘r2∥≤(O(1)+∥r1∥⋅∥r2∥)O(1)\lVert r_1 \circ r_2\rVert\leq(O(1)+\lVert r_1\rVert\cdot\lVert r_2\rVert)^{O(1)}.

Indeed, ignoring QQ for simplicity, Claim 19 follows immediately from [4 Thm. 6], similarly to Claim 16, as the composition r1∘r2r_1 \circ r_2 is the projection to the first and last coordinate of (r1×N)∩(N×r2)(r_1 \times\mathbb{N}) \cap(\mathbb{N} \times r_2).

Likewise we get the bound for images and inverse images of relations:

Claim 20. Semilinear relations r⊆(Q×N)2r \subseteq(Q \times\mathbb{N})^2 and semilinear sets X⊆Q×NX \subseteq Q \times\mathbb{N} satisfy ∥r∘X∥,∥X∘r∥≤(O(1)+∥r∥⋅∥X∥)O(1)\lVert r \circ X\rVert,\lVert X \circ r\rVert\leq(O(1)+\lVert r\rVert\cdot\lVert X\rVert)^{O(1)}.

Concerning the first part of Lemma 7, we bound the number of iterations of the transformation

S↦S∪(⇒−∘⇒0∗)∘S(20)S \mapsto S \cup(\Rightarrow_- \circ\Rightarrow^*_0) \circ S \tag*{(20)}

needed to compute the fixpoint Φ3∘{t}\Phi_{3} \circ\{t\}, starting from X0=(⇒−∘⇒0∗)∘{t}X_{0} = (\Rightarrow_{-} \circ\Rightarrow_{0}^{*}) \circ\{t\}. Due to Claims 18 and 20, the bases of the DD-saturated set X0X_{0} are bounded triply exponentially in nn. Then every base of every next DD-saturated set

Xi+1:=Xi∪(⇒−∘⇒0∗)∘Xi,X_{i+1} := X_i \cup(\Rightarrow_{-} \circ\Rightarrow_{0}^{*}) \circ X_i,

as Xi⊆Xi+1X_i \subseteq X_{i+1}, is either smaller than some base of XiX_i, or is newly created, namely MIN⁡(Xi+1)(q,r)=m<∞\operatorname{MIN}(X_{i+1})(q,r) = m < \infty while MIN⁡(Xi)(q,r)=∞\operatorname{MIN}(X_i)(q,r) = \infty for some q∈Qq \in Q and r∈{0…D−1}r \in\{0 \ldots D-1\}. A newly created base may appear at most ∣Q∣⋅D|Q| \cdot D times (exponentially many times) during the whole iteration. Again due to Claims 18 and 20, if a new base appears in Xi+1X_{i+1} then

∥Xi+1∥≤∥Xi∥O(1)⋅exp⁡3(poly⁡(n)),\lVert X_{i+1}\rVert\leq\lVert X_i\rVert^{O(1)} \cdot\exp_3(\operatorname{poly}(n)),

otherwise ∥Xi+1∥≤∥Xi∥\lVert X_{i+1}\rVert\leq\lVert X_i\rVert. In consequence, for every XiX_i we have

∥Xi∥≤(∥X0∥⋅exp⁡3(poly⁡(n)))2O(∣Q∣⋅D)(21)\lVert X_i\rVert\leq\left(\lVert X_0\rVert\cdot\exp_3(\operatorname{poly}(n))\right)^{2^{O(|Q|\cdot D)}} \tag*{(21)}

which yields a triply exponential bound on ∥Xi∥\lVert X_i\rVert. 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 {t}\{t\}, and we have actually shown:

Claim 21. Given a kk-exponentially semilinear set SS, k≥3k \geq3, the set Φ3∘S\Phi_3 \circ S is kk-exponentially semilinear and computable in at most kk-exponentially many iterations of (20).

Concerning the second part of Lemma 7, we need to bound the number of iterations of the transformation

S↦S∪f(S),where f(S)=S∘(⇒0∗∘Φ3∘⇒+),(22)S \mapsto S \cup f(S), \qquad\text{where } f(S) = S \circ(\Rightarrow_{0}^{*} \circ\Phi_3 \circ\Rightarrow_{+}), \tag*{(22)}

needed to compute the fixpoint {s}∘Φ1\{s\} \circ\Phi_1, starting from X0=f({s})X_0 = f(\{s\}). We should also provide an upper bound on computation of X0X_0, and computation of every iteration Xi+1:=Xi∪f(Xi)X_{i+1} := X_i \cup f(X_i).

We start by analyzing the computation of X0=f({s})X_0 = f(\{s\}). By Claim 17 the set (⇒+∘Xq,r)(\Rightarrow_{+} \circ X_{q,r}) is exponentially semilinear. Then by Claim 21 applied to k=3k = 3 and S=(⇒+∘Xq,r)S = (\Rightarrow_{+} \circ X_{q,r}), the set S′=Φ3∘(⇒+∘Xq,r)=(Φ3∘⇒+)∘Xq,rS' = \Phi_3 \circ(\Rightarrow_{+} \circ X_{q,r}) = (\Phi_3 \circ\Rightarrow_{+}) \circ X_{q,r} is computable in at most triply exponentially many iterations of the transformation (20), say mm iterations. Then intersection YY of S′S' with the set {s}∘⇒0∗\{s\} \circ\Rightarrow_{0}^{*},

Y=({s}∘⇒0∗)∩((Φ3∘⇒+)∘Xq,r),Y = (\{s\} \circ\Rightarrow_{0}^{*}) \cap((\Phi_3 \circ\Rightarrow_{+}) \circ X_{q,r}),

has (relying on Claims 18 and 16) bases and periods of at most triply exponential norm. Assume, w.l.o.g., that m=2ℓm = 2^{\ell} for some doubly exponential ℓ\ell, and let R=(⇒−∘⇒0∗)≤mR = (\Rightarrow_{-} \circ\Rightarrow_{0}^{*})^{\leq m}. The relation RR is computable by ℓ\ell-fold self-composition T↦T∪T2T \mapsto T \cup T^{2} starting from T=(⇒−∘⇒0∗)∪Id⁡T = (\Rightarrow_{-} \circ\Rightarrow_{0}^{*}) \cup\operatorname{Id}, each self-composition increasing the norm polynomially, which implies:

Claim 22. The relation RR is 4-exponentially semilinear.

We have Φ3∘(⇒+∘Xq,r)=R∘(⇒+∘Xq,r)\Phi_3 \circ(\Rightarrow_{+} \circ X_{q,r}) = R \circ(\Rightarrow_{+} \circ X_{q,r}). Now, a key observation is that once YY is nonempty, there is a pair (y,y′)∈Y×(⇒+∘Xq,r)(y,y') \in Y \times(\Rightarrow_{+} \circ X_{q,r}) such that (y,y′)∈R(y,y') \in R, which implies that the set

Y∘R∘⇒+Y \circ R \circ\Rightarrow_{+}

has necessarily nonempty intersection with Xq,rX_{q,r}, and moreover the intersection contains, due to Claims 17, 19, 20 and 22, a number which is at most 4-exponential in nn. 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 ∥X0∥\lVert X_0\rVert. Testing candidates in the exhaustive search requires only 4-exponentially many iterations of (20), due to Claim 21 (applied to k=4k=4).

When computing the iteration S↦S∪f(S)S \mapsto S \cup f(S), we only apply Claim 21 to sets of the form ⟹+∘Xq,r\Longrightarrow^{+} \circ X_{q,r}, which do not themselves depend on the input set SS. As such, the bound mm on the number of iterations does not depend on the input set SS either, and in the same way as above we obtain the same 4-exponential bound on the norm of every subsequent iterate Xi+1=Xi∪f(Xi)X_{i+1}=X_i\cup f(X_i).

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

∥Xi∥≤(∥X0∥⋅exp⁡4(poly⁡(n)))2O(∣Q∣⋅D),\lVert X_i\rVert\leq\left(\lVert X_0\rVert\cdot\exp_4(\operatorname{poly}(n))\right)^{2^{O(\lvert Q\rvert\cdot D)}},

which yields a 4-exponential bound on ∥Xi∥\lVert X_i\rVert. 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 nn, 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [23]Marvin Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967.
  24. [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. [25]Rohit Parikh. On context-free languages. J. ACM, 13(4):570–581, 1966.DOI
  26. [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. [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

Paper details

vlnc:W_xftgmm2q
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Large language models

View statement
Looking for related papers…
Contents