Makowsky, Janos A.

Blatter-Specker Theorem for ternary relations ★★

Author(s): Makowsky

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 \}$. For any class $C$ definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every $m \in \mathbb{N}$, the function $f_C(n)$ is ultimately periodic modulo $m$.

\begin{question} Does the Blatter-Specker Theorem hold for ternary relations. \end{question}

Keywords: Blatter-Specker Theorem; FMT00-Luminy

Syndicate content