Recent Talks

Deciding Equivalence of Top-Down Tree Transducers

Lille, May 9th, 2007 pdf-slides pdf-handout

  • Equivalence Problems of Transducers
  • Top-Down Tree Transducers
  • Uniform & Earliest
  • Regular Look-Ahead
  • Applications: Inclusion of XML Queries

    MSO Logic and Tree Transducers with Decidable Equivalence

    Tokyo, February 22nd, 2007 pdf-slides pdf-handout
    Edinburgh, January 24th, 2007 pdf-slides pdf-handout

  • MSO Definable Translations
  • Parikhs Theorem and Semilinear Sets
  • Deciding Equivalence of MSOTT
  • Applications

    Deciding Equivalence of Top-Down XML Transformations in Polynomial Time

    Nice, January 20th, 2007 pdf-slides pdf-handout

  • Equivalence Problems & Tree Transducers
  • Uniform & Earliest
  • Regular Look-Ahead
  • Applications: Inclusion of XML Queries

    Logic, Databases, and Formal Languages

    Canberra, December 5th, 2006 pdf-slides pdf-handout

  • Databases / finite model theory --> relational structures
  • Computation / complexity theory --> numbers
  • Automata / language theory --> ordered structures
  • Why Tree Automata??

    Open Problems in Tree Language Theory

    Bonn, June 7th, 2006 pdf-slides pdf-handout

  • Tree Languages and Tree Transducers
  • Logic
  • Rankedness versus Unrankedness

    The Equivalence Problem for Deterministic MSO Tree Transducers is Decidable

    Lille, June 2nd, 2006 pdf-slides pdf-handout

  • Equivalence Problems
  • Parikh's Theorem and Semilinear Sets
  • MSO Tree Transducers
  • Deciding Equivalence of MSOTTs
  • Applications

    Structural Selectivity Estimation for XML Documents

    Lille, May 4th, 2007
    Edinburgh, May 24th, 2006 pdf-slides pdf-handout

  • Motivation - Why Selectivity Estimation for XML?
  • Prior Approaches
  • Our Synopsis - Pruned SLT Grammars
  • Selectivity Estimation for Structural XPath - Count Automata over Pruned SLT Grammars
  • Updates
  • Conclusion and Future

    The Equivalence Problem for Deterministic MSO Tree Transducers is Decidable

    Hyderabad, December 18th, 2005 pdf-slides pdf-handout

  • Equivalence Problems in FLT
  • Parikhs Theorem and Semilinear Sets
  • MSO Tree Transducers (MSOTT)
  • Deciding Equivalence of MSOTTs

    Verification of Graph Properties Using Automata, Logic, and Context-Free Sets

    Sydney, November 8th, 2005 pdf-slides pdf-handout

  • Verification Spaces for Strings and Trees (FLT)
  • Verification Spaces for Graphs
  • MSO (Monadic Second-Order) Logic
  • Applications

    Grammar-Based Tree Compression

    Sydney, October 14th, 2005 pdf-slides pdf-handout
    Sydney, September 9th, 2005 pdf-slides pdf-handout
    Edinburgh, August 22nd, 2005. pdf-slides pdf-handout

  • Compressed Trees: DAGs and SL Grammars
  • Generating SL Grammars with BPLEX
  • Unranked vs. Binary Trees
  • Algorithms on SL Grammars: (1) Type Validation and (2) Equivalence Test

    The Equivalence Problem for Deterministic MSO Tree Transducers is Decidable

    Munich, July 7th, 2005 pdf-slides pdf-handout

  • Equivalence Problems
  • Parikh’s Theorem and Semilinear Sets
  • MSO Tree Transducers
  • Deciding Equivalence of MSOTTs
  • Future

    Tree Automata and XPath on Compressed Trees

    Nice, June 27th, 2005 pdf-slides pdf-handout

  • Compressed Trees: DAGs & SL Grammars
  • Tree Automata (TA)
  • Membership Problems
  • XML Type Checking
  • Conclusions

    Types and Representations for XML Documents

    Lausanne, April 11th, 2005 pdf-slides pdf-handout

    Foundations of XML Processing

    Sydney, March 22nd, 2005 pdf-slides pdf-handout

  • Motivation of XML
  • Data Models
  • Type Formalisms
  • XML Processing: (1) Type Checking (2) Implementation
  • Future Research
  • Conclusion

    Models of Tree Translation

    Leiden, May 26th, 2004 slides pdf-handout

  • History of Tree Transducers
  • Theory of Tree Transducers
  • Applications to XML Processing

    Tree Transducers and Tree Compressions

    Barcelona, March 31st, 2004 slides pdf-handout

  • Internal Tree Representations
  • Directed Acyclic Graphs (DAGs)
  • Sharing Graphs (Sgraphs)
  • ATTs and DAGs
  • MTTs and Sgraphs

    XML Support for Scala

    Muenchenwihler, March 16th, 2004 (with Burak Emir and Martin Odersky) slides pdf-handout

  • Modules are Objects
  • Pattern Matching over Class Hierarchies
  • Representing XML Documents
  • Matching in Sequences
  • Internal Tree Representations

    Collapse of the MTT Hierarchy for Functions of Linear Size Increase

    Bombay, Dec. 15th, 2003 pdf-file printer version

    Applications of Tree Transducers in XML Querying

    Dresden, Dec. 2nd, 2003 pdf-file printer version

  • Motivation: Why XML?
  • XML Types and XML Queries
  • First Application: Query Evaluation
  • Second Application: Type Checking
  • Conclusions / Further Research

    Theory of XML Transformations: Tree Transducers

    Paris, Jul 3rd, 2003 pdf-file printer version

  • Motivation: Why XML? Why Tree Transducers?
  • XML Types = Regular Tree Languages
  • XML Transformations = Tree Transducers
  • Applications:
    Type Checking
    ``Static Garbage Collection''
  • Efficient Subclasses
  • Conclusions / Further Research

    Lausanne, Feb 21st, 2003 pdf-file printer version

  • XML Types = Regular Tree Languages
  • XML Transformations = Tree Transducers
  • Applications:
    Type Checking
    Almost Always Type Checking
    ``Static Garbage Collection''
  • Efficient Subclasses
  • Conclusions / Further Research

    Trier, Feb. 11th, 2003 pdf-file printer version

  • XML Motivation
  • The n-Pebble Tree Transducer (n-PTT)
  • Result 1: Decomposition into 0-PTTs
  • Result 2: 0-PTT $\subseteq$ Macro Tree Transducer (MTT)
  • Result 3: As Query Languages: PTT = MTT
  • Type Checking Problems
  • Further Research Topics

    Oldenburg, Feb. 4th, 2003 pdf-file printer version

  • History of Tree Transducers
  • Four Properties and Applications of Macro Tree Transducers (MTTs)
  • XML Transformations: The Pebble Tree Transducer (PTT)
  • Comparison: PTT vs. MTT
  • Further Research Topics