On Nondeterministic Unranked Tree Automata with Sibling Constraints
Christof Löding, Wong Karianto · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2009
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.