Affiliations: Department of Mathematics, Aristotle University of Thessaloniki, G-54006 Thessaloniki, Greece. [email protected] | Department of Computer Science, University of Western Ontario, London, Ontario N6A 5B7, Canada. [email protected]
Note: [] Address for correspondence: Department of Mathematics, Aristotle University of Thessaloniki, G-54006 Thessaloniki, Greece.
Note: [] Address for correspondence: Department of Computer Science, University of Western Ontario, London, Ontario N6A 5B7, Canada.
Abstract: 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.
Keywords: tree automata, synchronization, pushdown stores
