|
Organizers |
All Input Variables Are Essential for Almost All Logical Tree Automata
by
Ilyia Gyudzhenov
South-west University, Bulgaria
Coauthors: Slavcho Shtrakov (South-west University, Bulgaria)
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 some papers of S.Jablonsky, A.Salomaa, K.Chimev etc.
The present paper derive some combinatorial results which shows that
the most of logical tree automata have the maximal complexity
w.r.t. their inputs.
It is shown that k-valued logic 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: March 8, 2001
Copyright © 2001 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 # cagi-23.