Re: need help on tree automata

Burak Emir <>
6 Mar 2000 00:31:28 -0500

          From comp.compilers

Related articles
need help on tree automata (Paul Johnston) (2000-02-27)
Re: need help on tree automata (Christian Stapfer) (2000-03-06)
Re: need help on tree automata (Burak Emir) (2000-03-06)
| List of all articles for this month |

From: Burak Emir <>
Newsgroups: comp.compilers
Date: 6 Mar 2000 00:31:28 -0500
Organization: EPFL Departement d'Informatique
References: 00-02-146
Keywords: theory

Hi Paul!

I must admit, I have never heard of the term, but:
(1 what they are) all finite state machines can be represented as
if you have an automaton that can be represented as a tree (="tree
as a consequence, you could code it as nested switch statements :
        1 -"a"->2 ... switch(c) { // state 1
        | case "a": nextch(); switch(c) ... //state 2
      "b" case "b": nextch(); switch(c) ... //state 3
      \/ // this is plain english isn't it ? :)

(2 strengths) surely a subset of regular languages, no loops allowed.

(3 apps ) fast keyword matching in a compiler ? (trading off space
for time)

(4 difficulty) the idea is not difficult. What can be difficult is
applying anything we know
                              about trees mathematically to automatons that represent

please correct me if there exists some other possible interpretation of
the term "tree automaton" like e.g. a finite state machine that takes a
tree as input (would be nice...)

Burak Emir

Post a followup to this message

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