Deciding Top-Down Determinism of Regular Tree Languages

Peter Leupold, Sebastian Maneth

It is well known that for a regular tree language it is decidable whether or not it can be recognized by a deterministic top-down tree automaton (DTA). However, the computational c…