Automata for Unranked Trees

Contents

• Introduction
• Definitions and Examples
• Unranked Trees and Hedges
• Hedge Automata
• Deterministic Automata
• Encodings and Closure Properties
• First-Child-Next-Sibling Encoding
• Extension Operator
• Closure Properties
• Weak Monadic Second Order Logic
• Decision Problems and Complexity
• Representations of Horizontal Languages
• Determinism and Completeness
• Membership
• Emptiness
• Inclusion
• Minimization
• Minimizing the Number of States
• Problems for Minimizing the Whole Representation
• Stepwise automata
• XML Schema Languages
• Document Type Definition (DTD)
• XML Schema
• Relax NG
• Exercises
• Bibliographic Notes