The following technical report is available from http://aib.informatik.rwth-aachen.de:
Unranked Tree Automata with Sibling Equalities and Disequalities Wong Karianto, Christof Löding AIB 2006-13
We propose an extension of the tree automata with constraints between direct subtrees (Bogaert and Tison, 1992) to unranked trees. Our approach uses MSO-formulas to capture the possibility of comparing unboundedly many direct subtrees. Our main result is that the nonemptiness problem for the deterministic automata, as in the ranked setting, is decidable. It turns out that the main difficulty is indeed the absence of the rank, as it gives a certain bound on the number of distinct subtrees needed in order to satisfy an equality or disequality constraint. We overcome this difficulty by finding such a bound via a brute-force method.
Keywords: (unranked) tree automata, monadic second-order logic, equality and disequality constraints