Branching Grammars: A Generalization of ET0L Systems

  • Frank Drewes
  • Joost Engelfriet
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


Generalizing ET0L systems, we introduce branching synchronization grammars with nested tables. Branching synchronization grammars with tables of nesting depth n have the same string- and tree-generating power as n-fold compositions of top-down tree transducers.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [Bak78]
    Brenda S. Baker. Tree transducers and tree languages. Information and Control, 37:241–266, 1978.zbMATHCrossRefMathSciNetGoogle Scholar
  2. [DE02]
    Frank Drewes and Joost Engelfriet. Branching Synchronization Grammars with Nested Tables. Technical Report UMINF 02.22, Umeå University, 2002.Google Scholar
  3. [Dre00]
    Frank Drewes. Tree-based picture generation. Theoretical Computer Science, 246:1–51, 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  4. [Dre01]
    Frank Drewes. Tree-based generation of languages of fractals. Theoretical Computer Science, 262:377–414, 2001.zbMATHCrossRefMathSciNetGoogle Scholar
  5. [Eng76]
    Joost Engelfriet. Surface tree languages and parallel derivation trees. Theoretical Computer Science, 2:9–27, 1976.zbMATHCrossRefMathSciNetGoogle Scholar
  6. [Eng82]
    Joost Engelfriet. Three hierarchies of transducers. Mathematical Systems Theory, 15:95–125, 1982.zbMATHCrossRefMathSciNetGoogle Scholar
  7. [ERS80]
    Joost Engelfriet, Grzegorz Rozenberg, and Giora Slutzki. Tree transducers, L systems, and two-way machines. Journal of Computer and System Sciences, 20:150–202, 1980.zbMATHCrossRefMathSciNetGoogle Scholar
  8. [FV98]
    Zoltán Fülöp and Heiko Vogler. Syntax-Directed Semantics: Formal Models Based on Tree Transducers. Springer, 1998.Google Scholar
  9. [GS84]
    Ferenc Gécseg and Magnus Steinby. Tree Automata. Akadémiai Kiadó, Budapest, 1984.zbMATHGoogle Scholar
  10. [GS97]
    Ferenc Gécseg and Magnus Steinby. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages. Vol. III: Beyond Words, chapter 1, pages 1–68. Springer, 1997.Google Scholar
  11. [Rou70]
    William C. Rounds. Mappings and grammars on trees. Mathematical Systems Theory, 4:257–287, 1970.zbMATHCrossRefMathSciNetGoogle Scholar
  12. [Roz73]
    Grzegorz Rozenberg. Extension of tabled 0L systems and languages. International Journal of Computer and Information Sciences, 2:311–334, 1973.CrossRefzbMATHMathSciNetGoogle Scholar
  13. [RS97]
    Grzegorz Rozenberg and Arto Salomaa, editors. Handbook of Formal Languages, volume 1–3. Springer, 1997.Google Scholar
  14. [Sky76]
    Sven Skyum. Decomposition theorems for various kinds of languages parallel in nature. SIAM Journal of Computing, 5:284–296, 1976.zbMATHCrossRefMathSciNetGoogle Scholar
  15. [Tha70]
    James W. Thatcher. Generalized2 sequential machine maps. Journal of Computer and System Sciences, 4:339–367, 1970.zbMATHMathSciNetGoogle Scholar
  16. [Tha73]
    James W. Thatcher. Tree automata: an informal survey. In A.V. Aho, editor, Currents in the Theory of Computing, pages 143–172. Prentice Hall, 1973.Google Scholar
  17. [Vág86]
    Sándor Vágvölgyi. On compositions of root-to-frontier tree transformations. Acta Cybernetica, 7:443–480, 1986.zbMATHMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Frank Drewes
    • 1
  • Joost Engelfriet
    • 2
  1. 1.Department of Computing ScienceUmeå UniversityUmeåSweden
  2. 2.Department of Computer ScienceLeiden UniversityLeidenThe Netherlands

Personalised recommendations