Learning a Regular Tree Language from a Teacher

  • Frank Drewes
  • Johanna Högberg
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


We generalize an inference algorithm by Angluin, that learns a regular string language from a “minimally adequate teacher”, to regular tree languages. This improves a similar algorithm proposed by Sakakibara. In particular, we show how our algorithm can be used to avoid dead states, thus answering a question by Sakakibara.


Transition Function Recursive Call Derivation Tree Tree Automaton Tree Language 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [Ang87]
    Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75:87–106, 1987.zbMATHCrossRefMathSciNetGoogle Scholar
  2. [Bra68]
    W.S. Brainerd. The minimalization of tree automata. Information and Computation, 13:484–491, 1968.zbMATHMathSciNetGoogle Scholar
  3. [Dre00]
    Frank Drewes. Tree-based picture generation. Theoretical Computer Science, 246:1–51, 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  4. [Eng94]
    Joost Engelfriet. Graph grammars and tree transducers. In S. Tison, editor, Proc. CAAP 94, volume 787 of Lecture Notes in Computer Science, pages 15–37. Springer, 1994.CrossRefGoogle Scholar
  5. [LJ78]
    L.S. Levy and A.K. Joshi. Skeletal structural descriptions. Information and Control, 39:192–211, 1978.zbMATHCrossRefMathSciNetGoogle Scholar
  6. [Sak90]
    Yasubumi Sakakibara. Learning context-free grammars from structural data in polynomial time. Theoretical Computer Science, 76:223–242, 1990.CrossRefzbMATHMathSciNetGoogle Scholar
  7. [TW68]
    James W. Thatcher and Jesse B. Wright. Generalized finite automata theory with an application to a decision-problem of second-order logic. Mathematical Systems Theory, 2:57–81, 1968.CrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Frank Drewes
    • 1
  • Johanna Högberg
    • 1
  1. 1.Department of Computing ScienceUmeå UniversityUmeåSweden

Personalised recommendations