2021/07/07 by Leupold, Peter, Maneth, Sebastian
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2107.03174
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 complexity of this problem has not been studied. We show that for a given deterministic bottom-up tree automaton it can be decided in quadratic time whether or not its language can be recognized by a DTA. Since there are finite tree languages that cannot be recognized by DTAs, we also consider finite unions of \DTAs and show that also here, definability within deterministic bottom-up tree automata is decidable in quadratic time.