Determinizing Alternating Tree Automata, and Models ?
Jean Goubault-Larrecq · 2006
While alternating or non-deterministic tree automata are syntax (e.g., clause sets), complete deterministic automata are best seen as semantics ( -algebras). In this sense, the powerset construction and the ltration construction are nite model constructions. We show that they are both instances of a more general construction. This leads to a determinization procedure that determinizes and minimizes partially at the same time.