The equivalence problem for deterministic MSO tree transducers is decidable.
Joost EngelfrietSebastian ManethPublished in: Inf. Process. Lett. (2006)
Keyphrases
- monadic second order logic
- regular expressions
- datalog programs
- expressive power
- tree automata
- finite automata
- query containment
- data complexity
- tree structure
- first order logic
- tree models
- transitive closure
- tree structures
- finite state
- classification trees
- binary tree
- decision trees
- tree patterns
- tree construction
- spanning tree
- query answering
- index structure