Extension Complexity, MSO Logic, and Treewidth.

Petr Kolman Martin Koutecký Hans Raj Tiwary

Published in: Discret. Math. Theor. Comput. Sci. (2020)

Keyphrases

space complexity
bounded treewidth
monadic second order logic
upper bound
regular expressions
search space
np complete
decision problems
expressive power
automated reasoning
worst case
modal logic
proof theoretic
temporal logic
classical logic
tree automata
relational databases
monadic datalog