Unsolved Problems

Conjecture Is the theory of the real numbers with the exponential function decidable?...

Question How many steps does it take the sixth Goodstein sequence to terminate?...

Question Can either of the following be expressed in fixed-point logic plus counting: - Given a graph, does it have a perfect matching, i.e., a set $...

Question - Does ${<}\text{-invariant\:FO} = \text{FO}$ hold over graphs of bounded tree-width? - Is ${<}\text{-invariant\:FO}$ included in $\text{MSO...

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic for...

Let $C$ be a class of finite relational structures. We denote by $f_C(n)$ the number of structures in $C$ over the labeled set $\{0, \dots, n-1 \}$. F...

Question Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linea...

Question Positive Horn logic (pH) is the fragment of FO involving exactly $\exists, \forall, \wedge, =$. Does the fragment $pH \wedge \neg pH$ have th...

Conjecture For every $\varepsilon > 0$ there is $\delta > 0$ such that, for every large $n$, there are $n$-vertex graphs $G$ and $H$ such that $G \equ...