My PhD Thesis:   "Models of Tree Translation"

Models of Tree Translation Introduction Tree Transducers The Generating Power of Tree Transducers MSO Tree Transducers and MTTs of Linear Size Increase Comparison of Pebble Tree Transducers with MTTs The Generating Power of Total Deterministic Tree Transducers Introduction Preliminaries Top-Down Tree Transducers, Attributed Tree Transducers, and Attribute Grammars Generating Power of Deterministic Top-Down Tree Transducers Term-Generating Power of Attribute Grammars and Attributed Tree Transducers A Hierarchy for the Generating Power of Attributed Tree Transducers Further Research Topics Output String Languages of Compositions of Deterministic Macro Tree Transducers Introduction Preliminaries Macro Tree Transducers Closure Properties Bridge Theorems The yMTT-Hierarchy and the EDT0L-Hierarchy The IO-Hierarchy Conclusions and Open Problems Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations Introduction Preliminaries Tree Transducers Top-Down and Attributed Relabelings Single Use Restricted Tree Transducers Finite Copying MTTs Main Result and Consequences Macro Tree Translations of Linear Size Increase are MSO Definable Introduction Preliminaries Macro Tree Transducers Finite Copying Restrictions Proper Normal Form From Linear Size Increase to Finite Copying Main Results and Consequences A Comparison of Pebble Tree Transducers with Macro Tree Transducers Introduction Preliminaries Pebble Tree Transducers Decomposition of Pebble Tree Transducers Pebble Tree Transducers and Macro Tree Transducers Pebble Hierarchies for Deterministic PTTs Type Checking Conclusions and Problems