On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth

Uffe Flarup Laurent Lyaudet

Published in: CoRR (2008)

Keyphrases

expressive power
bounded treewidth
first order logic
data complexity
transitive closure
query language
computational properties
databases
np complete
relational calculus
relational algebra
data model
decision problems
recursive queries
constraint query languages