6 Mar 2000 00:24:31 -0500

Related articles |
---|

need help on tree automata johnston.p@worldnet.att.net (Paul Johnston) (2000-02-27) |

Re: need help on tree automata chstapfer@bluewin.ch (Christian Stapfer) (2000-03-06) |

Re: need help on tree automata Burak.Emir@dimail.epfl.ch (Burak Emir) (2000-03-06) |

From: | "Christian Stapfer" <chstapfer@bluewin.ch> |

Newsgroups: | comp.compilers |

Date: | 6 Mar 2000 00:24:31 -0500 |

Organization: | Swisscom AG, the blue window |

References: | 00-02-146 |

Keywords: | theory |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.