<p>Yes/No = Non-deterministic automata are stronger: <a href="http://www.mimuw.edu.pl/~bojan/papers/dtwa.pdf" rel="noreferrer">http://www.mimuw.edu.pl/~bojan/papers/dtwa.pdf</a></p>

CC BY-SA 3.0
2011-05-09T05:49:49.833Z
2011-05-09T05:49:49.833Z
domotorp
<p>For tree automata, you have the following results:</p>

<ul>
<li><p>Deterministic bottom-up tree automata have the same expressive power as non-deterministic bottom-up tree automata. </p></li>
<li><p>Deterministic top-down tree automata are weaker than non-deterministic top-down tree automata.</p></li>
</ul>

<p>More details can be found in the <a href="http://tata.gforge.inria.fr/" rel="nofollow">Tree Automata</a> book.</p>

<p>It seems that you are interested in top-down tree automata, so the answer to your question is <strong>no</strong>. You will of course have to check whether top-down tree automata are in fact what you are interested in.</p>

CC BY-SA 3.0
2011-05-08T11:08:24.087Z
No, none of these, but the wiki article had a link to the notion that I defined: http://en.wikipedia.org/wiki/Tree_walking_automaton
domotorp
CC BY-SA 3.0
2011-05-08T08:17:55.997Z
2011-05-08T08:41:03.030Z
2011-05-08T08:41:03.030Z
Dave Clarke
<p>Update: It seems this problem has been studied and solved recently, see this wiki article: <a href="http://en.wikipedia.org/wiki/Tree_walking_automaton" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Tree_walking_automaton</a>
And also this survey:
<a href="http://www.mimuw.edu.pl/~bojan/papers/twasurvey.pdf" rel="nofollow noreferrer">http://www.mimuw.edu.pl/~bojan/papers/twasurvey.pdf</a></p>

<p>Suppose that instead of the usual set of words, {0,1}*, our words are not linear but rather given on some tree structure. To prevent our machines from "getting lost", define our words as the set of binary, embedded arborescences. (So every word is a tree, where every edge is directed away from a given a root that has degree two, every other non-leaf vertex has degree three, and every edge is labeled left or right such that any two edges starting from the same vertex have different labels.) A language is a set of such trees. (Note that there is no need to write zeros and ones on the vertices as they can be anyhow simulated by locally modifying the trees.) When a machine is "reading a tree", it starts from the root, it can sense if a given vertex is the root, a leaf or a degree three vertex and can decide if in the next step it wants to go to the parent of the vertex, or on the edge labeled left or right.</p>

<p>Is it true in this model that any language that can be recognized by a non-deterministic finite state automaton can also be recognized by a deterministic finite state automaton?</p>

<p>Note that when the tape is the usual linear tape, this is true, as any 2-NFA can be simulated with a 2-DFA (even with a DFA). I already asked a special instance of the problem <a href="https://cstheory.stackexchange.com/questions/3981/is-the-balanced-boolean-formula-problem-solvable-in-sublogarithmic-space-if-the-i">here</a> that was solved by <a href="https://cstheory.stackexchange.com/users/313/kristoffer-arnsfelt-hansen">Kristoffer</a>. The motivation would be to solve <a href="https://cstheory.stackexchange.com/questions/3963/does-loglog-nloglog">this</a>.</p>

CC BY-SA 3.0
2011-05-09T09:20:24.513Z
I would suggest modifying the title to mention "non-deterministic *tree-walking* automata".
Sylvain
<cc.complexity-theory><automata-theory><space-bounded><dfa>
Are non-deterministic tree-walking automata stronger than deterministic ones?
domotorp
# Are non-deterministic tree-walking automata stronger than deterministic ones?

(Asked by: username_0 on 2011-05-08)

Update: It seems this problem has been studied and solved recently, see this wiki article: <http://en.wikipedia.org/wiki/Tree_walking_automaton>
And also this survey:
<http://www.mimuw.edu.pl/~bojan/papers/twasurvey.pdf>

Suppose that instead of the usual set of words, {0,1}\*, our words are not linear but rather given on some tree structure. To prevent our machines from "getting lost", define our words as the set of binary, embedded arborescences. (So every word is a tree, where every edge is directed away from a given a root that has degree two, every other non-leaf vertex has degree three, and every edge is labeled left or right such that any two edges starting from the same vertex have different labels.) A language is a set of such trees. (Note that there is no need to write zeros and ones on the vertices as they can be anyhow simulated by locally modifying the trees.) When a machine is "reading a tree", it starts from the root, it can sense if a given vertex is the root, a leaf or a degree three vertex and can decide if in the next step it wants to go to the parent of the vertex, or on the edge labeled left or right.

Is it true in this model that any language that can be recognized by a non-deterministic finite state automaton can also be recognized by a deterministic finite state automaton?

Note that when the tape is the usual linear tape, this is true, as any 2-NFA can be simulated with a 2-DFA (even with a DFA). I already asked a special instance of the problem [here](https://cstheory.stackexchange.com/questions/3981/is-the-balanced-boolean-formula-problem-solvable-in-sublogarithmic-space-if-the-i) that was solved by [Kristoffer](https://cstheory.stackexchange.com/users/313/kristoffer-arnsfelt-hansen). The motivation would be to solve [this](https://cstheory.stackexchange.com/questions/3963/does-loglog-nloglog).

**Tags:** cc.complexity-theory, automata-theory, space-bounded, dfa

> **Comments:**
> **username_1**: I would suggest modifying the title to mention "non-deterministic *tree-walking* automata".  

---

## 2 answers

### Answer by username_0 on 2011-05-09. Score: 5 | Accepted answer

Yes/No = Non-deterministic automata are stronger: <http://www.mimuw.edu.pl/~bojan/papers/dtwa.pdf>


---

### Answer by username_2 on 2011-05-08. Score: 6

For tree automata, you have the following results:

* Deterministic bottom-up tree automata have the same expressive power as non-deterministic bottom-up tree automata.
* Deterministic top-down tree automata are weaker than non-deterministic top-down tree automata.

More details can be found in the [Tree Automata](http://tata.gforge.inria.fr/) book.

It seems that you are interested in top-down tree automata, so the answer to your question is **no**. You will of course have to check whether top-down tree automata are in fact what you are interested in.

> **Comments:**
> **username_0**: No, none of these, but the wiki article had a link to the notion that I defined: http://en.wikipedia.org/wiki/Tree_walking_automaton  

---

