Tree-walking automata cannot be determinized
Tree-walking automata are a natural sequential model for recognizing languages of finite trees. Such automata walk around the tree and may decide in the end to accept it. It is shown that deterministic tree-walking automata are weaker than nondeterministic tree-walking automata. (c) 2005 Elsevier B.V. All rights reserved.
tree-walking automata deterministic tree-walking automata