{#sec:NondetInitial}
--------------------------

Given a two-counter machine $\M$, we construct a one-counter net $\A$ as follows (see Figure \[fig:A\]). Intuitively, an input word $w$ to $\A$ is a sequence of segments separated by $\#$, where each segment is a sequence of commands from $\M$. Accordingly, the alphabet of $\A$ consists of $\#$ and all possible commands of $\M$. We build $\A$ to accept $w$, once starting with a big enough initial counter value, if one of the following conditions holds: i) one of $w$’s segments is shorter than the length of the (legal halting) run of $\M$; or ii) one of $w$’s segments does not respect the control structure underlying $\M$, which is called a “non-counting cheat” here; or iii) all of $w$’s segments do not describe a prefix of the run of $\M$, making “counting cheats”. The OCN reads every segment in between two $\#$’s starting in, and returning to, a central state $q_0$.

Non-counting cheats are easy to verify—for every line $l$ of $\M$, there is a corresponding state $q$ in $\A$, and when $\A$ is at state $q$ and reads a letter $a$, $\A$ checks if $a$ matches the command in $l$. For example, if $l=$ and $a=$ 