State Complexity of Projection and Quotient on Unranked Trees

We consider projection and quotient operations on unranked tree languages, and investigate their state complexities on deterministic unranked tree automata. We give a tight upper bound on the number of vertical states which is different than the known state complexity of projection for string language. Since there are two ways to define concatenation on trees, we define four different quotient operations on trees and obtain tight bounds for each operation. The state complexity of sequential bottom-quotient differs by a multiplicative factor (n+1) from the corresponding result of left-quotient on ordinary finite automata.