<p>Let $L$ be the set of sentences in some logic.  I am interested in cases where $L$ is the set of sentences in monadic second-order logic, or it is its $\Pi^1_1$ fragment.  Let $K$ be a class of finite structures.  The <em>theory</em> $\mathrm{Th}_L(K)$ of $K$ is the set of sentences $\phi$ such that $\forall M \in K$ $M \models \phi$.  I am interested in decidability of $\mathrm{Th}_L(K)$.</p>

<p>For what kind of class $K$ is this known?  What are important / deep techniques here?  What is a good source to learn the results and the techniques?</p>

CC BY-SA 3.0
2017-02-13T20:32:26.120Z
A starting point: https://en.wikipedia.org/wiki/Courcelle's_theorem
Sylvain
CC BY-SA 4.0
2018-11-01T07:35:31.517Z
This question asks for reference on MSO as well. So it may be useful to you:  https://math.stackexchange.com/q/2696251/120721
Cyriac Antony
<reference-request><lo.logic><finite-model-theory>
Decidability of the monadic second-order theory of a class of finite structures
Pteromys
# Decidability of the monadic second-order theory of a class of finite structures

(Asked by: username_0 on 2017-02-11)

Let $L$ be the set of sentences in some logic. I am interested in cases where $L$ is the set of sentences in monadic second-order logic, or it is its $\Pi^1\_1$ fragment. Let $K$ be a class of finite structures. The *theory* $\mathrm{Th}\_L(K)$ of $K$ is the set of sentences $\phi$ such that $\forall M \in K$ $M \models \phi$. I am interested in decidability of $\mathrm{Th}\_L(K)$.

For what kind of class $K$ is this known? What are important / deep techniques here? What is a good source to learn the results and the techniques?

**Tags:** reference-request, lo.logic, finite-model-theory

> **Comments:**
> **username_1**: A starting point: https://en.wikipedia.org/wiki/Courcelle's_theorem  
> **username_2**: This question asks for reference on MSO as well. So it may be useful to you:  https://math.stackexchange.com/q/2696251/120721  

---

## 0 answers

