Re: need help on tree automata

Burak Emir <Burak.Emir@dimail.epfl.ch>
6 Mar 2000 00:31:28 -0500

          From comp.compilers

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)
| List of all articles for this month |

From: Burak Emir <Burak.Emir@dimail.epfl.ch>
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
graphs.
if you have an automaton that can be represented as a tree (="tree
automaton"?,
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 ? :)
        3


(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
trees.


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.