<p>As <a href="https://cstheory.stackexchange.com/questions/50473/complexity-for-universal-counter-machine-with-0-1-valued-registers?noredirect=1#comment111271_50473">Marzio De Biasi states</a>, since <span class="math-container">$k$</span> is fixed, this is equivalent to a NFA.  To deal with the &quot;universal&quot; requirement, use the subset construction to convert to a DFA.</p>
<p>In particular: the state of the DFA is the set of configurations of the counter machine that can be reached after reading the input so far.  Since <span class="math-container">$k$</span> is fixed, there are only finitely many possible configurations of the counter machine, so only finitely many sets, so only finitely many states of the DFA.  The accepting state of the DFA is the singleton set containing <span class="math-container">$\langle q_f;0,\dots,0\rangle$</span>.</p>

CC BY-SA 4.0
2021-09-14T16:57:15.833Z
2021-09-14T16:57:15.833Z
D.W.
<p>Consider a <em>universal <span class="math-container">$\{0,1\}$</span>-<span class="math-container">$k$</span>-counter machine</em> where each of the <span class="math-container">$k$</span> registers has a value in <span class="math-container">$\{0,1\}$</span> (as opposed to any non-negative integer in the usual formulation), and there are states <span class="math-container">$q_1, .., q_f$</span> with <span class="math-container">$q_1$</span> initial and <span class="math-container">$q_f$</span> final. The set of instructions are chosen from the following: <em>increment</em> <span class="math-container">$q_a {+}r_j q_b$</span> i.e. when in state <span class="math-container">$q_a$</span> increment register <span class="math-container">$r_j$</span> from <span class="math-container">$0$</span> to <span class="math-container">$1$</span> and transition to state <span class="math-container">$q_b$</span>, <em>decrement</em> <span class="math-container">$q_a {-}r_j q_b$</span> i.e. similar to before but from <span class="math-container">$1$</span> to <span class="math-container">$0$</span>, and <em>forking</em> from <span class="math-container">$&lt;q_a; n_1, .., n_k&gt;$</span> to <span class="math-container">$&lt;q_b; n_1, .., n_k&gt;$</span> and <span class="math-container">$&lt;q_c; n_1, .., n_k&gt;$</span>.</p>
<p>The machine is non-deterministic in the sense that more than one instruction may be applicable to a configuration, and universal because a configuration is accepted iff <em>every</em> branch in the computation tree leads to <span class="math-container">$&lt;q_f; 0, .., 0&gt;$</span>.</p>
<p>i) What is the name for such a CM ? (surely this machine, or an equivalent formulation, must have been studied..)</p>
<p>ii) What is the complexity lower bound for determining if there is a computation from a given configuration <span class="math-container">$&lt;q_i; n_1, .., n_k&gt;$</span> such that every leaf in the computation tree is <span class="math-container">$&lt;q_f; 0, .., 0&gt;$</span> ?</p>
<p><strong>EDIT</strong> Given a universal <span class="math-container">$\{0,1\}$</span>-<span class="math-container">$k$</span>-counter machine C (as per description in question) we can decide if it accepts <span class="math-container">$w \in \{0,1\}^k$</span> using a TM that accepts input <span class="math-container">$&lt;C,w&gt;=n$</span> in <span class="math-container">$2^{O(n)}$</span> time by generating all computation trees of height <span class="math-container">$1,2, .., 2^k$</span> (<span class="math-container">$\leq 2^n$</span>). Thus acceptance can be decided in EXPTIME. What is lacking is the lower bound.</p>
<p>Added MathJax equations</p>

CC BY-SA 4.0
2021-09-13T11:19:51.517Z
Is $k$ fixed? If yes, then the model should be equivalent to a simple  NFA
Marzio De Biasi
CC BY-SA 4.0
2021-09-13T20:49:04.230Z
The definition of the machine is incomplete.  You tell us what the set of allowable instructions is, but how is the set of applicable instructions for a particular configuration chosen?  What does it depend on?  Please give a complete mathematical definition of the semantics of this machine.
D.W.
CC BY-SA 4.0
2021-09-14T05:04:45.063Z
@Marzio, for any given machine, the k is fixed. I don't see the encoding you have in mind. For example, how would the NFA would account for the universal property where the configuration is accepted if all the children in the computation tree accept.
RRRR
CC BY-SA 4.0
2021-09-14T05:14:36.830Z
@D.W. What I described is the definition of the abstract machine. A concrete machine is obtained by choosing (however you wish) some subset of applicable instructions. This is similar to how there is an abstract definition of a Turing machine, and a concrete TM is obtained by choosing a concrete set of states, transition function etc.
RRRR
<automata-theory><time-complexity><lower-bounds><turing-machines><counter-automata>
Complexity for universal Counter Machine with {0,1}-valued registers
RRRR
# Complexity for universal Counter Machine with {0,1}-valued registers

(Asked by: username_0 on 2021-09-12)

Consider a *universal $\{0,1\}$-$k$-counter machine* where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q\_1, .., q\_f$ with $q\_1$ initial and $q\_f$ final. The set of instructions are chosen from the following: *increment* $q\_a {+}r\_j q\_b$ i.e. when in state $q\_a$ increment register $r\_j$ from $0$ to $1$ and transition to state $q\_b$, *decrement* $q\_a {-}r\_j q\_b$ i.e. similar to before but from $1$ to $0$, and *forking* from $$ to $$ and $$.

The machine is non-deterministic in the sense that more than one instruction may be applicable to a configuration, and universal because a configuration is accepted iff *every* branch in the computation tree leads to $$.

i) What is the name for such a CM ? (surely this machine, or an equivalent formulation, must have been studied..)

ii) What is the complexity lower bound for determining if there is a computation from a given configuration $$ such that every leaf in the computation tree is $$ ?

**EDIT** Given a universal $\{0,1\}$-$k$-counter machine C (as per description in question) we can decide if it accepts $w \in \{0,1\}^k$ using a TM that accepts input $=n$ in $2^{O(n)}$ time by generating all computation trees of height $1,2, .., 2^k$ ($\leq 2^n$). Thus acceptance can be decided in EXPTIME. What is lacking is the lower bound.

Added MathJax equations

**Tags:** automata-theory, time-complexity, lower-bounds, turing-machines, counter-automata
> **Comments:**
> **username_1**: Is $k$ fixed? If yes, then the model should be equivalent to a simple  NFA  
> **username_2**: The definition of the machine is incomplete.  You tell us what the set of allowable instructions is, but how is the set of applicable instructions for a particular configuration chosen?  What does it depend on?  Please give a complete mathematical definition of the semantics of this machine.  
> **username_0**: @Marzio, for any given machine, the k is fixed. I don't see the encoding you have in mind. For example, how would the NFA would account for the universal property where the configuration is accepted if all the children in the computation tree accept.  
> **username_0**: @D.W. What I described is the definition of the abstract machine. A concrete machine is obtained by choosing (however you wish) some subset of applicable instructions. This is similar to how there is an abstract definition of a Turing machine, and a concrete TM is obtained by choosing a concrete set of states, transition function etc.  

---

## 1 answers

### Answer by username_2 on 2021-09-14. Score: 2

As [Marzio De Biasi states](https://cstheory.stackexchange.com/questions/50473/complexity-for-universal-counter-machine-with-0-1-valued-registers?noredirect=1#comment111271_50473), since $k$ is fixed, this is equivalent to a NFA. To deal with the "universal" requirement, use the subset construction to convert to a DFA.

In particular: the state of the DFA is the set of configurations of the counter machine that can be reached after reading the input so far. Since $k$ is fixed, there are only finitely many possible configurations of the counter machine, so only finitely many sets, so only finitely many states of the DFA. The accepting state of the DFA is the singleton set containing $\langle q\_f;0,\dots,0\rangle$.


---

