4 E. FISCHER, T. KOTEK, AND J.A. MAKOWSKY
(ii) Every Specker sequence a(n) is computable, and in fact it is in the count-
ing class · PH, [49], where PH is the polynomial hierarchy and the
input n is measured in unary presentation. Hence a(n) is computable in
exponential time, and using polynomial space.
(iii) The set of Specker sequences is closed under the point-wise operations
of addition and multiplication. The same holds for MSOL-Specker se-
quences.
We shall discuss examples of sequences a(n) which have a combinatorial inter-
pretation in great detail in Part 2. Among them we find the counting functions for
trees, graphs, planar graphs, binomial coefficients, factorials, and many more. The
reader may want to consult the The On-Line Encyclopedia of Integer Sequences
(OEIS) [1] which contains close to 200 000 integer sequences studied in the litera-
ture. The non-monotonic sequence a(n) beginning with
1, 1, 1, 2, 5, 4, 7, 6, 7, 9, 11, 10, 13, 13, 13, 14,
17, 16, 19, 18, 19, 21, 23, 22, 25, 25, 25, 26, 29,
28, 31, 30, 31, 33, 35, 34, 37, 37, 37, 38, 41, (A085801)
23, 22, 25, 25, 25, 26, 29, 28, 31, 30, 31, 33,
35, 34, 37, 37, 37, 38, 41, 40, 43, 42, 43, 45, 47,
46, 49, 49, 49, 50, 53, 52, 55, 54, 55, 57, 59, 58, . . .
appears there as Sequence A085801 which has an ordered combinatorial interpreta-
tion as the maximum number of nonattacking queens on an (n × n) toroidal board.
A more theoretical source is the erudite monograph [32].
To the best of our knowledge no systematic study of sequences a(n) which have
a combinatorial interpretation has been undertaken so far. Notable exceptions are
the cases where K is a graph property which is hereditary (closed under induced
subgraphs) or monotone (closed under subgraphs), cf. [72, 5, 6, 4].
Problem 1.
(i) Characterize the sequences of integers which have (pure) combinatorial
interpretations under various restrictions imposed on K. What are the
additional restrictions on the counting function besides those listed in
Proposition 1.1?
(ii) Characterize the L-Specker sequences for various sublogics of SOL.
In this paper we investigate sufficient conditions for Specker sequences to satisfy
linear recurrence relations. We also study the converse question: For a given class
of linear recurrence relations REC, can we find a family of logical interpretations I
such that every sequence in REC has a logical interpretation in I?
2. Linear recurrences
We are in particular interested in linear recurrence relations which may hold
over Z or Zm.
Definition 2.1 (Recurrence relations). Given a sequence a(n) of integers we
say a(n) is
4
Previous Page Next Page