On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic.

Stephan Kreutzer Siamak Tazari

Published in: SODA (2010)

Keyphrases

monadic second order logic
expressive power
regular expressions
tree automata
np complete
first order logic
data complexity
databases
database systems
lower bound
domain knowledge
query language
data integration
pattern matching
context sensitive
grid computing