<p>I just randomly started fooling around with formal languages, grammars, and machines, and I have an extension to DFAs that I do not know what the class of languages it can recognize is.</p>
<p>I'll give a formal definition below.</p>
<p>Let's define this <span class="math-container">$n$</span>-counter DFA as a 5-tuple, similar to a normal DFA <span class="math-container">$$M = (Q, \Sigma, \eta : Q \times \mathcal{P}(I_n) \times \Sigma \to Q \times \mathbb{Z}^n, q_0 \in Q, F \subseteq Q) $$</span>
Where <span class="math-container">$I_n = \{1, \cdots, n\}$</span>, and <span class="math-container">$\mathcal{P}$</span> denotes the power set.</p>
<p>For ease of reference, let us say that <span class="math-container">$\eta(q, z, s) \equiv (\eta_q(q, z, s), \eta_c(q, z, s))$</span>, defined in the natural way.</p>
<p>Let us call a <em>configuration</em> of <span class="math-container">$M$</span> as a member of <span class="math-container">$C = Q \times \mathbb{Z}^n$</span>. From here, let us define the actual transition function, <span class="math-container">$\delta : C \times \Sigma \to C$</span>, in terms of <span class="math-container">$\eta$</span>:
<span class="math-container">$$\delta( (q, c) \in C, s \in \Sigma ) := (\eta_q(q,\{i\in I_n|c_i = 0\},s), \\c+\eta_c(q, \{i \in I_n|c_i=0\},s))$$</span></p>
<p>With addition on tuples being defined element-wise, and members of tuples being accessed by subscripts, and 1-indexed.</p>
<p>Similarly let us extend this transition function to a <span class="math-container">$\delta^\ast : C \times \Sigma^\ast\to C$</span> as follows:
<span class="math-container">$$
\delta^\ast((q, c) \in C, \varepsilon \in \Sigma^\ast) := (q, c) \\
\delta^\ast((q, c) \in C, \langle s \rangle \in \Sigma^\ast) := \delta((q, c), s) \forall s \in \Sigma\\
\delta^\ast((q, c) \in C, sx \in \Sigma^\ast) := \delta^\ast(\delta((q, c), s), x) \forall s \in \Sigma, x \in \Sigma^\ast
$$</span>
And as well define our initial configuration as <span class="math-container">$C_0 := (q_0, \langle 0, \cdots, 0\rangle \in \mathbb{Z}^n)$</span>, and define whether a string <span class="math-container">$s$</span> is accepted as:
<span class="math-container">$$ s \in L(M) \Leftrightarrow \delta^\ast(C_0, s) \in F \times \{\langle 0, \cdots, 0 \rangle\} $$</span></p>
<p>I've constructed a few of these <span class="math-container">$n$</span>-counter DFAs that can recognize a wide variety of languages from different levels in the Chomsky hierarchy, such as <span class="math-container">$$
\{0^n1^n | n \geq 1\} \\
\{0^n1^n2^n | n \geq 1\} \\
\{a^mb^nc^md^n | m, n \geq 0\} \\
\{(ab^n)^n | n \geq 0\}
$$</span>
(That last one I need to double-check, but I think my construction works)</p>
<p>I've noticed that the forced consumption of a symbol per transition vastly cripples the machine, as if we were to allow <span class="math-container">$\epsilon$</span>-transitions, I am fairly sure that a n-counter DFA with <span class="math-container">$\epsilon$</span>-transitions is able to simulate a n-register Minsky machine with <span class="math-container">$n$</span> registers fairly directly, so we have TCness past a point.</p>
<p>I was wondering whether this class of languages had been investigated in some form before, I know that <a href="https://en.wikipedia.org/wiki/Counter_automaton" rel="nofollow noreferrer">something similar, albeit with only <span class="math-container">$n=1$</span>. and <span class="math-container">$\epsilon$</span>-transitions being allowed,</a> has been worked on a bit.</p>

CC BY-SA 4.0
2022-09-22T19:01:16.477Z
This is not precisely a counter machine, because the 0-tests are only at the end. But it is a well-studied variant, see e.g., Vector Addition Systems, Counter Automata, Minsky Machines.
Shaull
CC BY-SA 4.0
2022-09-23T00:01:00.313Z
@EmilJeřábek see the newly updated version, I have added an accurate definition.
Adalynn
CC BY-SA 4.0
2022-09-23T07:43:16.790Z
Thank you. I removed my comments that are no longer relevant. As an upper bound, languages accepted by counter DFA are computable in one-way logspace (1L), as studied in https://epubs.siam.org/doi/10.1137/0210027 .
Emil Jeřábek
CC BY-SA 4.0
2022-09-23T08:36:36.273Z
Which also explains why it cannot recognize palindromes: it is easy to see that any one-way machine recognizing palindromes needs space $\Omega(n)$.
Emil Jeřábek
CC BY-SA 4.0
2022-09-23T08:51:23.600Z
In fact, if you allow $\epsilon$-transitions, but keep the counters restricted so that they can only hold numbers of value $O(n)$, then you get exactly 1L. (Without the restriction on values, the model with $\epsilon$-transitions is Turing-complete, as noted.)
Emil Jeřábek
CC BY-SA 4.0
2022-09-23T13:12:00.457Z
In absence of $\epsilon$-transitions, the requirement that all counters be $0$ for acceptance is very limiting, as the machine has to “plan ahead” to clear them, which needs a hint from the input that the end is nigh. For example, it’s easy to see that the only *unary* languages recognizable by counter DFA are those that are regular (i.e., semilinear/eventually periodic), whereas if we drop the condition on clearing counters, we can recognize various other languages such as $\{1^{n^2}:n\in\mathbb N\}$.
Emil Jeřábek
CC BY-SA 4.0
2022-09-23T17:14:23.577Z
So just merely having the accept condition to $ \in F \times \mathbb{Z}^n$ would work to get to $\{1^{n^2} | n \in \mathbb{N} \}$? Or is it changing it to some zero-checks like in transitions?
Adalynn
CC BY-SA 4.0
2022-09-23T19:13:23.977Z
Just $F\times\mathbb Z^n$ will work, but if you also allow some zero-checks, it will be easier. I think these two versions of the computation model are likely equivalent, actually.
Emil Jeřábek
CC BY-SA 4.0
2022-09-24T08:21:35.373Z
One more comment (I’ll stop, promise). There exists a language recognizable by a counter DFA (even with the $F\times\{\vec0\}$ stopping condition) which is L-complete under DLOGTIME reductions. The language consists of sequences of functions $f_0,\dots,f_{m-1}\colon[n]\to[n]$ such that $f_{m-1}(\dots(f_0(0))\dots)=0$, encoded as “$f_0(0),\dots,f_0(n-1);f_1(0),\dots,f_1(n-1);\dots;f_{m-1}(0),\dots,f_{m-1}(n-1);$” using delimiters ‘,’ and ‘;’, with each value written in unary. We also allow padding symbols ‘_’ to appear freely anywhere (this facilitates completeness under DLOGTIME reductions).
Emil Jeřábek
<fl.formal-languages>
Languages recognized Counter DFA
Adalynn
# Languages recognized Counter DFA

(Asked by: username_0 on 2022-09-22)

I just randomly started fooling around with formal languages, grammars, and machines, and I have an extension to DFAs that I do not know what the class of languages it can recognize is.

I'll give a formal definition below.

Let's define this $n$-counter DFA as a 5-tuple, similar to a normal DFA $$M = (Q, \Sigma, \eta : Q \times \mathcal{P}(I\_n) \times \Sigma \to Q \times \mathbb{Z}^n, q\_0 \in Q, F \subseteq Q) $$
Where $I\_n = \{1, \cdots, n\}$, and $\mathcal{P}$ denotes the power set.

For ease of reference, let us say that $\eta(q, z, s) \equiv (\eta\_q(q, z, s), \eta\_c(q, z, s))$, defined in the natural way.

Let us call a *configuration* of $M$ as a member of $C = Q \times \mathbb{Z}^n$. From here, let us define the actual transition function, $\delta : C \times \Sigma \to C$, in terms of $\eta$:
$$\delta( (q, c) \in C, s \in \Sigma ) := (\eta\_q(q,\{i\in I\_n|c\_i = 0\},s), \\c+\eta\_c(q, \{i \in I\_n|c\_i=0\},s))$$

With addition on tuples being defined element-wise, and members of tuples being accessed by subscripts, and 1-indexed.

Similarly let us extend this transition function to a $\delta^\ast : C \times \Sigma^\ast\to C$ as follows:
$$
\delta^\ast((q, c) \in C, \varepsilon \in \Sigma^\ast) := (q, c) \\
\delta^\ast((q, c) \in C, \langle s \rangle \in \Sigma^\ast) := \delta((q, c), s) \forall s \in \Sigma\\
\delta^\ast((q, c) \in C, sx \in \Sigma^\ast) := \delta^\ast(\delta((q, c), s), x) \forall s \in \Sigma, x \in \Sigma^\ast
$$
And as well define our initial configuration as $C\_0 := (q\_0, \langle 0, \cdots, 0\rangle \in \mathbb{Z}^n)$, and define whether a string $s$ is accepted as:
$$ s \in L(M) \Leftrightarrow \delta^\ast(C\_0, s) \in F \times \{\langle 0, \cdots, 0 \rangle\} $$

I've constructed a few of these $n$-counter DFAs that can recognize a wide variety of languages from different levels in the Chomsky hierarchy, such as $$
\{0^n1^n | n \geq 1\} \\
\{0^n1^n2^n | n \geq 1\} \\
\{a^mb^nc^md^n | m, n \geq 0\} \\
\{(ab^n)^n | n \geq 0\}
$$
(That last one I need to double-check, but I think my construction works)

I've noticed that the forced consumption of a symbol per transition vastly cripples the machine, as if we were to allow $\epsilon$-transitions, I am fairly sure that a n-counter DFA with $\epsilon$-transitions is able to simulate a n-register Minsky machine with $n$ registers fairly directly, so we have TCness past a point.

I was wondering whether this class of languages had been investigated in some form before, I know that [something similar, albeit with only $n=1$. and $\epsilon$-transitions being allowed,](https://en.wikipedia.org/wiki/Counter_automaton) has been worked on a bit.

**Tags:** fl.formal-languages
> **Comments:**
> **username_1**: This is not precisely a counter machine, because the 0-tests are only at the end. But it is a well-studied variant, see e.g., Vector Addition Systems, Counter Automata, Minsky Machines.  
> **username_0**: @EmilJeřábek see the newly updated version, I have added an accurate definition.  
> **username_2**: Thank you. I removed my comments that are no longer relevant. As an upper bound, languages accepted by counter DFA are computable in one-way logspace (1L), as studied in https://epubs.siam.org/doi/10.1137/0210027 .  
> **username_2**: Which also explains why it cannot recognize palindromes: it is easy to see that any one-way machine recognizing palindromes needs space $\Omega(n)$.  
> **username_2**: In fact, if you allow $\epsilon$-transitions, but keep the counters restricted so that they can only hold numbers of value $O(n)$, then you get exactly 1L. (Without the restriction on values, the model with $\epsilon$-transitions is Turing-complete, as noted.)  
> **username_2**: In absence of $\epsilon$-transitions, the requirement that all counters be $0$ for acceptance is very limiting, as the machine has to “plan ahead” to clear them, which needs a hint from the input that the end is nigh. For example, it’s easy to see that the only *unary* languages recognizable by counter DFA are those that are regular (i.e., semilinear/eventually periodic), whereas if we drop the condition on clearing counters, we can recognize various other languages such as $\{1^{n^2}:n\in\mathbb N\}$.  
> **username_0**: So just merely having the accept condition to $ \in F \times \mathbb{Z}^n$ would work to get to $\{1^{n^2} | n \in \mathbb{N} \}$? Or is it changing it to some zero-checks like in transitions?  
> **username_2**: Just $F\times\mathbb Z^n$ will work, but if you also allow some zero-checks, it will be easier. I think these two versions of the computation model are likely equivalent, actually.  
> **username_2**: One more comment (I’ll stop, promise). There exists a language recognizable by a counter DFA (even with the $F\times\{\vec0\}$ stopping condition) which is L-complete under DLOGTIME reductions. The language consists of sequences of functions $f_0,\dots,f_{m-1}\colon[n]\to[n]$ such that $f_{m-1}(\dots(f_0(0))\dots)=0$, encoded as “$f_0(0),\dots,f_0(n-1);f_1(0),\dots,f_1(n-1);\dots;f_{m-1}(0),\dots,f_{m-1}(n-1);$” using delimiters ‘,’ and ‘;’, with each value written in unary. We also allow padding symbols ‘_’ to appear freely anywhere (this facilitates completeness under DLOGTIME reductions).  

---

## 0 answers

