Expressive power of monadic logics on words, trees, pictures, and graphs.
Oliver MatzNicole SchweikardtPublished in: Logic and Automata (2008)
Keyphrases
- expressive power
- monadic second order logic
- transitive closure
- data complexity
- first order logic
- query language
- relational algebra
- computational properties
- datalog queries
- deductive databases
- recursive queries
- directed graph
- graph matching
- datalog programs
- closure properties
- finite automata
- query containment
- relational calculus
- logic programming