Events

Fall 2016

# Fellows Logic Open Seminar

Oct 31, 2016 2:00 pm – 3:30 pm

Parent Program:

Speaker:

Location:

Calvin Lab Rm 116

## Monadic Second Order Finite Satisfiability and Unbounded Tree-Width

The finite satisfiability problem of monadic second order logic is decidable only on classes of structures of bounded tree-width by the classic result of Seese. We prove that the following problem is decidable:

Input: (i) A monadic second order logic sentence alpha, and (ii) a sentence beta in the two-variable fragment of first order logic extended with counting quantifiers. The vocabularies of alpha and beta may intersect.

Output: Is there a finite structure which satisfies alpha and beta such that the restriction of the structure to the vocabulary of alpha has bounded tree-width? (The tree-width of the desired structure is not bounded.)