Atlas home ||
Conferences |
Abstracts |
about Atlas
AAA60: Workshop on General Algebra (60. Arbeitstagung Allgemeine Algebra)
June 22-25, 2000
Dresden University of Technology
Dresden, Germany |
|
Organizers
Reinhard Pöschel, Manfred Droste, Bernhard Ganter
View Abstracts
Conference Homepage |
Tree Automata and Essential Input Variables
by
Slavcho Shtrakov
South-West University, Blagoevgrad
Tree Automata and Essential Input Variables
Tree Automata and Essential Input Variables
Slavcho Shtrakov
Abstract
The consideration that finite automata may be viewed as
unary algebras is attributed to J.Büchi and J.Wright (1960).
In the many of the papers
trees were defined as terms. Investigations on regular and
context-free tree grammars are dated in the late 60-th.
The algebraic theory of terms was created and developed to
equational theory in the works of A.Malc'ev, G.Grätzer etc. approximately
in the same time. Later it is developed by many researchers -
J.Rosenberg, K.Denecke, D.Lau, R.Pöshel etc.
In the papers of S.Jablonsky, A.Salomaa, K.Chimev etc.
the theory of essential variables for functions was developed.
The present paper is an attempt to connect these three fields of
theoretical computer science. We introduce the essential inputs (variables)
for terms (trees) and tree automata . There are
investigations which treat some rules for removing and adding fictive
(non-essential) inputs to a term. We consider a new point of view on the
minimization of tree-automata and tree-languages. Such minimization is
realized by a procedure (algorithm).
AMS 1991, subject classification: 03D05, 68Q68, 68Q70, 03D15, 06B25
Dept. of Computer Science
South-West University
2700 Blagoevgrad, Bulgaria
e-mail: shtrakov@aix.swu.bg
http://www.cs.swu.bg
Date received: May 18, 2000
Copyright © 2000 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 # caee-36.