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.

Authors

• Mikołaj Bojańczyk
• Thomas Colcombet

Keywords

• Tree-walking automata
• Deterministic tree-walking automata