Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable.
Helmut SeidlSebastian ManethGregor KemperPublished in: FOCS (2015)
Keyphrases
- datalog programs
- tree structure
- suffix tree
- data structure
- tree construction
- finite state automata
- string matching
- tree models
- tree edit distance
- query containment
- index structure
- tree structures
- binary tree
- approximate string matching
- arbitrary length
- edit operations
- database
- spanning tree
- edit distance
- pattern matching
- knowledge base
- databases