On the Boolean Closure of Deterministic Top-Down Tree Automata

International Journal of Foundations of Computer Science, vol. 35, pp. 11–22

Abstract

The class of Boolean combinations of tree languages recognized by deterministic top-down tree automata (also known as deterministic root-to-frontier automata) is studied. The problem of determining for a given regular tree language whether it belongs to this class is open. We provide some progress by two results: First, a characterization of this class by a natural extension of deterministic top-down tree automata is presented, and as an application we obtain a convenient method to show that certain regular tree languages are outside this class. In the second result, it is shown that, for fixed [Formula: see text], it is decidable whether a regular tree language is a Boolean combination of [Formula: see text] tree languages recognized by deterministic top-down tree automata.

Authors 2

1. Christof Löding corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Informatik 7, Aachen, Germany

2. Wolfgang Thomas Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Informatik 7, Aachen, Germany