On the Size of Stack and Synchronization Alphabets of Tree Automata
George Rahonis, Kai Salomaa · Fundamenta Informaticae · 1998
We consider classes of forests defined by synchronized and pushdown tree automata having a fixed size of, respectively, synchronization or pushdown alphabet. We show that such families have nice properties, for instance, they form either a sheaf or a strict alphabetic cone of forests. Furthermore, for the (deterministic and nondeterministic) synchronized tree automata and the real-time pushdown tree automata we obtain a strict infinite forest hierarchy with respect to the alphabet size.