All Input Variables Are Essential for Almost All Trees and Logical Tree Automata
by
Slavcho Shtrakov
South West University
Coauthors: Ilya Gyudzhenov

In many papers the trees were defined as terms. As in the word case there are many results concerning automata working over trees. The theory of essential variables was developed in the work of S.Jablonsky, A.Salomaa, K.Chimev etc.
The present paper derive some combinatorial results which show that almost all of the logical tree automata have the maximal complexity w.r.t. their inputs. It is shown that k-valued logics can be interpreted as tree languages recognized by logical automata. This means that the most of results obtained for k-valued functions are valid for logical tree automata.

Date received: December 20, 2002