Deterministic top-down tree automata: past, present, future

Abstract

In strong contrast to their non-deterministic counterparts, deterministic top-down tree automata received little attention in the scientific literature. The aim of this article is to survey recent and less recent results and stipulate new research directions for top-down deterministic tree automata motivated by the advent of the XML data exchange format. In particular, we survey different ranke and unranked top-down tree automata models and discuss expressiveness, closure properties and the complexity of static analysis problems.