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

Copyright © 2002 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cake-09.