The Complexity of Checking Non-Emptiness in Symbolic Tree Automata

Rodrigo Raya

We study the satisfiability problem of symbolic tree automata and decompose it into the satisfiability problem of the existential first-order theory of the input characters and the…