<p>This model is one of the standard models in automata theory and it has been examined by some researchers. </p>

<p>The references given in the first comment are very good starting points. </p>

<p>When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. However, when the head is one-way, then, up to my knowledge, we do not have a similar exact characterization, but, we have certain incomparable results and some hierarchies based on the number of heads. </p>

<p>If you are interested in, I recommend you to check alternating, probabilistic, and quantum versions of multi-head automata, as well. Such models can be quite interesting even when using a single head, as the computation is split in into different paths, and then, in each path, the head may access different part of the inputs.</p>

<p><strong>Some generic references:</strong></p>

<ul>
<li>Turing Machines with Sublogarithmic Space - <a href="https://books.google.lv/books?id=vNPuNOo9BUYC" rel="noreferrer">https://books.google.lv/books?id=vNPuNOo9BUYC</a></li>
</ul>

<p><em>Alternation</em></p>

<ul>
<li>Viliam Geffert - <a href="https://dblp.uni-trier.de/pers/hd/g/Geffert:Viliam" rel="noreferrer">https://dblp.uni-trier.de/pers/hd/g/Geffert:Viliam</a></li>
</ul>

<p><em>Probabilistic computation</em></p>

<ul>
<li>Ioan I. Macarie - <a href="https://dblp.org/pers/hd/m/Macarie:Ioan_I=" rel="noreferrer">https://dblp.org/pers/hd/m/Macarie:Ioan_I=</a></li>
</ul>

<p><em>Probabilistic and quantum computation</em></p>

<ul>
<li>Rusins Freivalds - <a href="https://dblp.uni-trier.de/pers/hd/f/Freivalds:Rusins" rel="noreferrer">https://dblp.uni-trier.de/pers/hd/f/Freivalds:Rusins</a></li>
<li>Abuzer Yakaryilmaz - <a href="https://dblp.uni-trier.de/pers/hd/y/Yakaryilmaz:Abuzer" rel="noreferrer">https://dblp.uni-trier.de/pers/hd/y/Yakaryilmaz:Abuzer</a></li>
</ul>

<p><strong>Related models:</strong> multi-counter automata and automata using pebble.</p>

CC BY-SA 4.0
2019-10-06T20:53:18.483Z
2019-10-06T20:59:05.987Z
2019-10-06T20:59:05.987Z
Abuzer Yakaryilmaz
<p>A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have <em>multiple heads</em>, each of which moves through the input from left-to-right, but not necessarily at the same place in the input as the others.</p>
<p>Let us define a finite state machine with <span class="math-container">$k$</span> heads as follows:</p>
<blockquote>
<p>A <strong>k-head NFA</strong> is a tuple <span class="math-container">$(Q, \Sigma, \Delta, q_0, F)$</span>, where:</p>
<ul>
<li><p>As usual, <span class="math-container">$Q$</span> is a finite set of states, <span class="math-container">$\Sigma$</span> is a finite alphabet, <span class="math-container">$q_0$</span> is an initial state, and <span class="math-container">$F$</span> is a set of accepting states. Let <span class="math-container">$\Sigma_\varepsilon := \Sigma \cup \{\varepsilon\}$</span> denote the set of characters including the empty string.</p>
</li>
<li><p><span class="math-container">$\Delta \subseteq Q \times (\Sigma_\varepsilon)^k \times Q$</span> is the transition relation: a transition <span class="math-container">$(p, (\sigma_1, \sigma_2, \ldots, \sigma_k), q)$</span> means that, if the machine is in state <span class="math-container">$p$</span>, it may read in <span class="math-container">$(\sigma_1, \sigma_2, \ldots, \sigma_k)$</span> such that <span class="math-container">$\sigma_i$</span> is the next character for head <span class="math-container">$i$</span> (or <span class="math-container">$\varepsilon$</span> if that head does not move), and then move to state <span class="math-container">$q$</span>.</p>
</li>
</ul>
<p>A run of this kind of machine (any path starting from the start state and ending in an accepting state) results in not one string, but <span class="math-container">$k$</span> different strings (formed by concatenating the characters along the run). Then we say that the run is <strong>valid</strong> if the <span class="math-container">$k$</span> strings are identical.</p>
<p>The <strong>language</strong> of the machine is the set of strings <span class="math-container">$w$</span> such that there exists a valid run of the machine where the <span class="math-container">$k$</span> strings produced along that run are all equal to <span class="math-container">$w$</span>.</p>
</blockquote>
<p><strong>Question:</strong> What is the class of languages recognized by such machines? Has it been studied?</p>
<hr />
<p>A first observation is that such machines produce a class larger than the regular languages. For example, the language
<span class="math-container">$$
\{a^n b^n \mid n \in \mathbb{N}\}
$$</span>
is recognized by the following <span class="math-container">$2$</span>-head NFA with <span class="math-container">$3$</span> states:
<img src="https://i.sstatic.net/lLClF.png" alt="2-head NFA example" /></p>
<p>(Here, an edge labeled with <span class="math-container">$\sigma_1 / \sigma_2$</span> denotes a transition of the form <span class="math-container">$(p, (\sigma_1, \sigma_2), q)$</span>.)</p>
<p>However, a second observation is that not all context-free languages are recognized; for example, it seems that the <a href="https://en.wikipedia.org/wiki/Dyck_language" rel="noreferrer">Dyck language</a> cannot be recognized by these <span class="math-container">$k$</span>-head machines.</p>

CC BY-SA 4.0
2019-10-04T17:15:32.957Z
Looking a bit around I see multi-head automata being mentioned in https://arxiv.org/abs/0906.3051: their definition is about two-way automata, but they also define the one-way variant. Isn't there something helpful in that paper? or in its references, e.g., https://www.sciencedirect.com/science/article/pii/S0304397509006288
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-10-04T17:32:34.843Z
Also note that they can recognize non CF languages: a 3 head DFA can recognize $a^n b^n c^n\#$; a good reference source: Markus Holzer and Martin Kutrib; Multi-Head Finite Automata: Characterizations, Concepts
and Open Problems
Marzio De Biasi
CC BY-SA 4.0
2019-10-04T17:51:00.443Z
Thanks for the paper references -- this was just an idle curiosity and I had not checked out the literature. If no one else does, I will read some literature and respond with an answer which summarizes the known results.
Caleb Stanford
CC BY-SA 4.0
2021-02-05T11:47:33.710Z
You might be interested in this paper (https://hal.archives-ouvertes.fr/hal-02301651/document), where for studying formal proofs, a model of multihead automaton is introduced, where the heads are 1-way but a head can jump to the location of an other head. This model turns out to be equivalent to LogSpace ie 2-way multihead automata.
Denis
<fl.formal-languages><automata-theory><regular-language><nfa>
What class of languages is recognized by finite-state automata with $k$ heads?
Caleb Stanford
# What class of languages is recognized by finite-state automata with $k$ heads?

(Asked by: username_0 on 2019-10-04)

A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have *multiple heads*, each of which moves through the input from left-to-right, but not necessarily at the same place in the input as the others.

Let us define a finite state machine with $k$ heads as follows:

> A **k-head NFA** is a tuple $(Q, \Sigma, \Delta, q\_0, F)$, where:
>
> * As usual, $Q$ is a finite set of states, $\Sigma$ is a finite alphabet, $q\_0$ is an initial state, and $F$ is a set of accepting states. Let $\Sigma\_\varepsilon := \Sigma \cup \{\varepsilon\}$ denote the set of characters including the empty string.
> * $\Delta \subseteq Q \times (\Sigma\_\varepsilon)^k \times Q$ is the transition relation: a transition $(p, (\sigma\_1, \sigma\_2, \ldots, \sigma\_k), q)$ means that, if the machine is in state $p$, it may read in $(\sigma\_1, \sigma\_2, \ldots, \sigma\_k)$ such that $\sigma\_i$ is the next character for head $i$ (or $\varepsilon$ if that head does not move), and then move to state $q$.
>
> A run of this kind of machine (any path starting from the start state and ending in an accepting state) results in not one string, but $k$ different strings (formed by concatenating the characters along the run). Then we say that the run is **valid** if the $k$ strings are identical.
>
> The **language** of the machine is the set of strings $w$ such that there exists a valid run of the machine where the $k$ strings produced along that run are all equal to $w$.

**Question:** What is the class of languages recognized by such machines? Has it been studied?

---

A first observation is that such machines produce a class larger than the regular languages. For example, the language
$$
\{a^n b^n \mid n \in \mathbb{N}\}
$$
is recognized by the following $2$-head NFA with $3$ states:
![2-head NFA example](https://i.sstatic.net/lLClF.png)

(Here, an edge labeled with $\sigma\_1 / \sigma\_2$ denotes a transition of the form $(p, (\sigma\_1, \sigma\_2), q)$.)

However, a second observation is that not all context-free languages are recognized; for example, it seems that the [Dyck language](https://en.wikipedia.org/wiki/Dyck_language) cannot be recognized by these $k$-head machines.

**Tags:** fl.formal-languages, automata-theory, regular-language, nfa

> **Comments:**
> **username_1**: Looking a bit around I see multi-head automata being mentioned in https://arxiv.org/abs/0906.3051: their definition is about two-way automata, but they also define the one-way variant. Isn't there something helpful in that paper? or in its references, e.g., https://www.sciencedirect.com/science/article/pii/S0304397509006288  
> **username_2**: Also note that they can recognize non CF languages: a 3 head DFA can recognize $a^n b^n c^n\#$; a good reference source: Markus Holzer and Martin Kutrib; Multi-Head Finite Automata: Characterizations, Concepts and Open Problems  
> **username_0**: Thanks for the paper references -- this was just an idle curiosity and I had not checked out the literature. If no one else does, I will read some literature and respond with an answer which summarizes the known results.  
> **username_3**: You might be interested in this paper (https://hal.archives-ouvertes.fr/hal-02301651/document), where for studying formal proofs, a model of multihead automaton is introduced, where the heads are 1-way but a head can jump to the location of an other head. This model turns out to be equivalent to LogSpace ie 2-way multihead automata.  

---

## 1 answers

### Answer by username_4 on 2019-10-06. Score: 5 | Accepted answer

This model is one of the standard models in automata theory and it has been examined by some researchers.

The references given in the first comment are very good starting points.

When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. However, when the head is one-way, then, up to my knowledge, we do not have a similar exact characterization, but, we have certain incomparable results and some hierarchies based on the number of heads.

If you are interested in, I recommend you to check alternating, probabilistic, and quantum versions of multi-head automata, as well. Such models can be quite interesting even when using a single head, as the computation is split in into different paths, and then, in each path, the head may access different part of the inputs.

**Some generic references:**

* Turing Machines with Sublogarithmic Space - <https://books.google.lv/books?id=vNPuNOo9BUYC>

*Alternation*

* Viliam Geffert - <https://dblp.uni-trier.de/pers/hd/g/Geffert:Viliam>

*Probabilistic computation*

* Ioan I. Macarie - <https://dblp.org/pers/hd/m/Macarie:Ioan_I=>

*Probabilistic and quantum computation*

* Rusins Freivalds - <https://dblp.uni-trier.de/pers/hd/f/Freivalds:Rusins>
* username_4 - <https://dblp.uni-trier.de/pers/hd/y/Yakaryilmaz:Abuzer>

**Related models:** multi-counter automata and automata using pebble.


---

