2026-08-03T12:49:37Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:19669 2024-03-06T11:04:36Z ddc:004 open_access
Extensions and Limits of the Specker-Blatter Theorem Fischer, Eldar Makowsky, Johann A. Specker-Blatter Theorem Monadic Second Order Logic MC-finiteness The original Specker-Blatter Theorem (1983) was formulated for classes of structures π’ž of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set [n] is modularly C-finite (MC-finite). In previous work we extended this to structures definable in CMSOL, MSOL extended with modular counting quantifiers. The first author also showed that the Specker-Blatter Theorem does not hold for one quaternary relation (2003). If the vocabulary allows a constant symbol c, there are n possible interpretations on [n] for c. We say that a constant c is hard-wired if c is always interpreted by the same element j ∈ [n]. In this paper we show: (i) The Specker-Blatter Theorem also holds for CMSOL when hard-wired constants are allowed. The proof method of Specker and Blatter does not work in this case. (ii) The Specker-Blatter Theorem does not hold already for π’ž with one ternary relation definable in First Order Logic FOL. This was left open since 1983. Using hard-wired constants allows us to show MC-finiteness of counting functions of various restricted partition functions which were not known to be MC-finite till now. Among them we have the restricted Bell numbers B_{r,A}, restricted Stirling numbers of the second kind S_{r,A} or restricted Lah-numbers L_{r,A}. Here r is an non-negative integer and A is an ultimately periodic set of non-negative integers. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Eldar Fischer and Johann A. Makowsky 2024 Is Part Of LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2024.26 urn:nbn:de:0030-drops-196694 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.26 eng https://creativecommons.org/licenses/by/4.0/legalcode