Re: need help on tree automata

Paul Johnston <johnston.p@worldnet.att.net> wrote:
> I'm trying to figure out what 'tree automata' is all about, but
> information is scarce or generally too theoretical for me.
As no one has yet answered you, I'll give it a try..


> I would really appreciate if someone could explain (in plain english)
You forgot to mention what an answer would be allowed to assume.
I suppose your posting this message to comp.compilers means that
you know about finite automata and the basics of compiler construction
but do not expect a very technical answer ('plain English').


> (1) basic summary of what they are
As the name says, they are automata operating on trees instead of
plain old strings (some would prefer to say: 'operating on terms',
but never mind that). An example may help:
Take the expression (a + b) * (c + 4), parse it and represent it
as an abstract syntax tree, then assign values to the variables
(say: a:= 1, b:= 2, c:=3), evaluate that tree from bottom up,
replacing operator nodes by intermediate results as you move
from the leaves towards the root, as in the following sequence:
        (1 + 2) * (3 + 4) --> 3 * (3 + 4) --> 3 * 7 --> 21
Assuming that the value 21 has been defined to be an accepting
state of this tree automaton, the automaton is said to accept
the tree, otherwise to reject it.
So this kind of tree automaton requires us to specify:
1. an assignments of values to variables,
2. a set of accepting states (values),
3. and, of course, suitably structured trees to operate on
(this is where free algebras, or term algebras as they are
often called, come in).
Tree automata are not normally defined as modifying trees ,
but, again, never mind about that. Evaluating expressions in this
manner is done by what is known as a (deterministic) bottom-u
tree automaton. There are top-down tree automata as well, and,
as you might have guessed, there are non-deterministic
bottom-up and top-down tree automata as well: four basic
kinds of tree automata in all..


> (2) what their main strengths are
The theory of tree automata gives you, for example, minimization
theorems, and different characterizations (bottom-up, top-down,
deterministic vs. non-deterministic, by regular tree expressions,
by tree grammars) of sets of trees that are 'recognizable' by
the various types of tree automata. ('Recognizable' sets of trees
are sets of trees, the members of which can be distinguished
from non-members by a tree automaton).


> (3) what kinds of applications benefit / require them?
Compiler construction, structured text handling


> (4) how conceptually 'difficult' you think they are (i.e. is this
> truly difficult or just always expressed in a very formal manner?)
The basic theory is not difficult (see, e.g., the book 'Tree Automata'
by Ferenc Gecseg and Magnus Steinby), but you'll have to learn the
fundamentals of what is called 'universal algebra'. This involves
getting acquainted with such things as universal algebras,
free (term) algebras, morphisms, lattices, and congruence relations.
Maybe these notions from universal algebra are what you take
to be 'very formal manners'? - But the theory of ordinary
finite automata, operating on strings, and the theory of
context-free languages are, generally speaking, just as formal
as the theory of tree automata :)
Hope this helps and doesn't sound too off-putting,
Christian

Return to the comp.compilers page.
Search the comp.compilers archives again.