Cooperating Tree and Graph Grammars

Brno, Aug. 21st, 1998
Leiden, Oct. 8th, 1997

  • [Title]
  • CD (string) grammars [1] [2] [3]
  • CD-REGT grammars in t-mode [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
  • CD-HR grammars [1] [2] [3] [4] [5]

    Tree Languages Generated by cf. Graph Grammars

    Paderborn, Nov. 20th, 1998
    Leiden, Nov. 4th, 1998

  • [Title]
  • HR Grammars generating trees [1] [2] [3] [4] [5]
  • Macro Tree Transducers (MTTs) [1] [2]
  • (the) two ways to generate trees: [1] (i) trees with external leaves [1] [2], (ii) leaf-linked forests [1] [2],
  • Result: tree-HR = MTT_fc(REGT) [1] [2] [3] [4] [5]

    Tree Transductions defined by Monadic Second Order Logic

    Szeged, Nov. 24th, 1998
    Leiden, May 29th, 1997

  • [Title]
  • Monadic Second Order (MSO) logic [1] [2]
  • MSO definable graph languages [1]
  • MSO definable graph functions [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
  • Tree Transducers [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]
  • MSOTT in MTT [1]

    String Languages Generated by Macro Tree Transducers

    Amsterdam, March 24th, 1999

  • [Title]
  • Syntax Directed Semantics [1] [2] [3]
  • Top-Down / Macro Tree Transducers [1] [2]
  • Yield Languages yMTT_sp(L) [1]
  • Bridge Theorem for yMTT(L) [1] [2] [3] [4] [5] [6]
  • Bridge Theorem for yMTT(L) [1]

    MSO Definability of Macro Tree Transductions is Decidable

    Leiden, May 26th, 1999
    Dresden, Apr. 20th, 1999

  • [Title]
  • Top-Down Tree Transducers (TOPTs) [1] [2] [3]
  • MSO Tree Transducers (MSOTs) [1] [2] [3] [4]
  • Finite Copying [1] [2] [3] [4]
  • Linear Size Increase (lsi) [1] [2] [3] [4] [5]
  • Macro Tree Transducers (MACTs) [1] [2] [3] [4]
  • Open Problems [1] [2] [3]

    Structured Document Transformations Based on XSL

    Kinloch Rannoch (Scotland), Sept. 1st, 1999

  • [Title]
  • Intro [1] [2] [3] [4]
  • XSL (eXtensive Style sheet Language) [1] [2]
  • DTL (Document Transformation Language) [1] [2] [3] [4] [5]
  • A Computation Model: Top-Down Tree Transducer [1] [2]
  • Outlook [1]

    Characterizing and Deciding MSO-definability of Macro Tree Transductions

    Lille, Feb. 19th, 2000

  • [Title]
  • Intro [1] [2] [3]
  • MSO definable tree transductions [1] [2]
  • Macro tree transducers [1] [2] [3]
  • Lsi MAC's are MSO definable [1] [2] [3]
  • Open Problems [1]

    Hierarchies of String Languages Generated by Deterministic Tree Transducers

    Vienna, July 18yh, 2001
    Leiden, July 5th, 2001

  • [Title]
  • EDT0L systems [1] [2] [3]
  • Iteration of control [1] [2]
  • The EDT0L-hierarchy is proper [1] [2] [3] [4] [5]
  • (Tree transducer hierarchies) [1]

    Two-Way Finite State Transducers with Nested Pebbles

    Warszawa, Aug. 26th, 2002

  • [Title]
  • Introduction [1] [2] [3]
  • The Two-Way FST with Nested Pebbles [1] [2]
  • Decomposition [1] [2]
  • Composition [1]
  • Typechecking [2]
  • Open Problems / Work in Progress [1]

    The Complexity of Compositions of Deterministic Tree Transducers

    Kanpur (India), Dec. 12th, 2002

  • [Title]
  • The translation problem [1] [2]
  • Main result and examples [1] [2] [3]
  • How to make an MTT garbage-free [1] [2]
  • Garbage remma and consequences [1] [2]
  • More results [1] [2]
  • Further research [1]