@inproceedings{10.1007/3-540-45071-8_11,
    Abstract = {In this paper we study the generating function of classes of graphs and hypergraphs modulo a fixed natural number m. For a class of labeled graphs C we denote by fc(n) the number of structures of size n. For C definable in Monadic Second Order Logic MSOL with unary and binary relation symbols only, E. Specker and C. Blatter showed in 1981 that for every m ∈ N, fc(n) satisfies a linear recurrence relation {\$}{\$}fc(n) = {\backslash}sum{\backslash}limits{\\_}{\{}j = 1{\}}^{\{}d{\\_}m {\}} {\{}a{\\_}j^{\{}(m){\}} fc(n - j),{\}} {\$}{\$}over ℤm, and hence is ultimately periodic for each m. In this paper we show how the Specker-Blatter Theorem depends on the choice of constants and relations allowed in the definition of C. Among the main results we have the following:For n-ary relations of degree at most d, where each element a is related to at most d other elements by any of the relations, a linear recurrence relation holds, irrespective of the arity of the relations involved.In all the results MSOL can be replaced by CMSOL, Monadic Second Order Logic with (modular) Counting. This covers many new cases, for which such a recurrence relation was not known before.},
    Address = {Berlin, Heidelberg},
    Author = {Fischer, E. and Makowsky, J. A.},
    BookTitle = {Computing and Combinatorics},
    Editor = {Warnow, Tandy and Zhu, Binhai},
    File = {The Specker-Blatter Theorem Revisited - fischer2003.pdf},
    ISBN = {978-3-540-45071-9},
    Pages = {90--101},
    Publisher = {Springer Berlin Heidelberg},
    Title = {The Specker-Blatter Theorem Revisited},
    Year = {2003},
    date-added = {2023-08-26 08:43:47 +0200},
    date-modified = {2023-08-26 08:43:47 +0200},
    doi = {10.1007/3-540-45071-8_11}
}

@inproceedings{10.1007/3-540-45071-8_11, Abstract = {In this paper we study the generating function of classes of graphs and hypergraphs modulo a fixed natural number m. For a class of labeled graphs C we denote by fc(n) the number of structures of size n. For C definable in Monadic Second Order Logic MSOL with unary and binary relation symbols only, E. Specker and C. Blatter showed in 1981 that for every m ∈ N, fc(n) satisfies a linear recurrence relation {\$}{\$}fc(n) = {\backslash}sum{\backslash}limits{\}{{}j = 1{}}^{{}d{\}m {}} {{}a{\_}j^{{}(m){}} fc(n - j),{}} {\$}{\$}over ℤm, and hence is ultimately periodic for each m. In this paper we show how the Specker-Blatter Theorem depends on the choice of constants and relations allowed in the definition of C. Among the main results we have the following:For n-ary relations of degree at most d, where each element a is related to at most d other elements by any of the relations, a linear recurrence relation holds, irrespective of the arity of the relations involved.In all the results MSOL can be replaced by CMSOL, Monadic Second Order Logic with (modular) Counting. This covers many new cases, for which such a recurrence relation was not known before.}, Address = {Berlin, Heidelberg}, Author = {Fischer, E. and Makowsky, J. A.}, BookTitle = {Computing and Combinatorics}, Editor = {Warnow, Tandy and Zhu, Binhai}, File = {The Specker-Blatter Theorem Revisited - fischer2003.pdf}, ISBN = {978-3-540-45071-9}, Pages = {90--101}, Publisher = {Springer Berlin Heidelberg}, Title = {The Specker-Blatter Theorem Revisited}, Year = {2003}, date-added = {2023-08-26 08:43:47 +0200}, date-modified = {2023-08-26 08:43:47 +0200}, doi = {10.1007/3-540-45071-8_11} }