Tree Automata and Essential Subtrees
by
Slavcho Shtrakov
South-West University, Blagoevgrad, Bulgaria

The algebraic theory of terms (trees) has been created and developed to the equational theory in the work of A.Malc'ev, G.Grätzer etc. In the papers of S.Jablonsky, A.Salomaa, K.Chimev etc. the theory of essential variables was developed. In the last years many authors studied tree automata in connection with theoretical computer science.
The present paper treats problems in the border of these three fields. We introduce essential subtrees for terms (trees) and tree automata . There are some results concerning independent sets of subtrees and separable sets for a tree and an automaton. It is proved that sets of independent positions are suffix closed and sets of essential subtrees are prefix closed.

AMS, subject classification: 03D05, 68Q70, 03D15, 06B25
Key words and phrases: Tree, Tree Automata, Essential Position, Essential Subtree, Independent Set, Separable Set.

Date received: March 8, 2001