On Nondeterministic Unranked Tree Automata with Sibling Constraints

Christof LöDing & Karianto Wong
We continue the study of bottom-up unranked tree automata with equality and disequality constraints between direct subtrees. In particular, we show that the emptiness problem for the nondeterministic automata is decidable. In addition, we show that the universality problem, in contrast, is undecidable.