On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices.
Uffe FlarupPascal KoiranLaurent LyaudetPublished in: ISAAC (2007)
Keyphrases
- expressive power
- bounded treewidth
- query language
- np complete
- transitive closure
- first order logic
- computational properties
- data complexity
- relational algebra
- conjunctive queries
- matching algorithm
- decision problems
- relational calculus
- fixed parameter tractable
- database
- pattern matching
- utility function
- logic programs
- programming language
- probability distribution
- data model
- search algorithm
- knowledge base