On the size of stack and synchronization alphabets of tree automata

• Autorzy: Rahonis G. , Salomaa K.
• Języki publikacji: EN

Abstrakty

EN

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 from 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.

Słowa kluczowe

EN

tree automata; synchronization; pushdown stores

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1998
• Tom: Vol. 36, nr 1
• Strony: 57--69
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Rahonis G.

autor

Salomaa K.

• Department of Mathematics, Aristotle University of Thessaloniki, G-54006 Thessaloniki, Greece,