The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable.
Joost EngelfrietSebastian ManethPublished in: FSTTCS (2005)
Keyphrases
- monadic second order logic
- tree automata
- expressive power
- finite automata
- datalog programs
- data complexity
- tree structure
- regular expressions
- first order logic
- hierarchical structure
- query language
- query containment
- finite state
- index structure
- r tree
- database
- tree patterns
- fixpoint
- binary tree
- data management
- tree construction
- database systems
- decision trees