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.

Abstract The original Specker–Blatter theorem (1983) was formulated for classes of structures $\mathcal {C}$ 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 \in [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 $\mathcal {C}$ 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 a non-negative integer and A is an ultimately periodic set of non-negative integers.

Let $T(G;X,Y)$ be the Tutte polynomial for graphs. We study the sequence $t_{a,b}(n) = T(K_n;a,b)$ where $a,b$ are non-negative integers, and show that for every $\mu \in \N$ the sequence $t_{a,b}(n)$ is ultimately periodic modulo $\mu$ provided $a \neq 1 \mod{\mu}$ and $b \neq 1 \mod{\mu}$. This result is related to a conjecture by A. Mani and R. Stones from 2016. The theorem is a consequence of a more general theorem which holds for a wide class of graph polynomials definable in Monadic Second Order Logic and some of its extensions, such as the the independence polynomial, the clique polynomial, etc. We also show similar results for the various substitution instances of the bivariate matching polynomial and the trivariate edge elimination polynomial $\xi(G;X,Y,Z)$ introduced by I. Averbouch, B. Godlin and the second author in 2008. All our results depend on the Specker-Blatter Theorem from 1981, which studies modular recurrence relations of combinatorial sequences which count the number of labeled graphs. Comment: Accepted for publication in Fundamenta Informaticae 186(3): 1-19 (2022), the special volume celebrating B.A. Trakhtenbrot's centenary

We study the exact learnability of real valued graph parameters f which are known to be representable as partition functions which count the number of weighted homomorphisms into a graph H with vertex weights alpha and edge weights beta. M. Freedman, L. Lovasz and A. Schrijver have given a characterization of these graph parameters in terms of the k-connection matrices C(f,k) of f. Our model of learnability is based on D. Angluin's model of exact learning using membership and equivalence queries. Given such a graph parameter f, the learner can ask for the values of f for graphs of their choice, and they can formulate hypotheses in terms of the connection matrices C(f,k) of f. The teacher can accept the hypothesis as correct, or provide a counterexample consisting of a graph. Our main result shows that in this scenario, a very large class of partition functions, the rigid partition functions, can be learned in time polynomial in the size of H and the size of the largest counterexample in the Blum-Shub-Smale model of computation over the reals with unit cost.

Using a theorem of N. Chomsky and M. Schützenberger one can characterize sequences of integers which satisfy linear recurrence relations with constant coefficients (C-finite sequences) as differences of two sequences counting words in regular languag

The 7th International Conference on Lattice Path Combinatorics and Applications was held in Sienna from 4-7 July, 2010, and was organized by the Dipartimento di Scienze Matematiche e Informatiche, University of Sienna, in cooperation with the Dipartimento di Sistemi e Informatica, University of Florence.Papers were sought in a wide spectrum of areas, for instance, lattice path enumeration, bijective and algebraic combinatorics, non parametric statistical inference, random walks, discrete distribution, analysis of algorithms, graph theory, and queueing theory.A large Scientif c Committee, guaranteeing wide coverage of subtopics and expertise in a variety of f elds, selected 37 papers for presentation as talks, and selected 14 other papers for presentation as posters.Furthermore, one plenary lecture was given by Anthony J. Guttmann, University of Melbourne, an outstanding researcher in combinatorics who studied several models of lattice paths.The present volume collects18enriched and extended versions of the papers presented in Sienna.All papers have been referred and we thank all referees for their assistance.Altogether, the papers collected here offer a snapshot of current research.At the same time, they illustrate the numerous ramif cations of the combinatorics of lattice paths throughout statistics, mathematics and computer science.Thus we hope that this volume will serve both as a reference text and as an introduction to many fascinating aspects of this f eld.

Many graph polynomials, such as the Tutte polynomial, the interlace polynomial and the matching polynomial, have both a recursive definition and a defining subset expansion formula. In this article, we present a general, logic-based framework which gives a precise meaning to recursive definitions of graph polynomials. We then prove in this framework that every recursive definition of a graph polynomial can be converted into a subset expansion formula.

Abstract. We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic ( CMSOL ) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k , for some fixed k . We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ -structures. This includes the cases where the models of ϕ are of tree width at most k . For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic GSOL . We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle. Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result.

Relational structures offer a common framework for handling graphs and hypergraphs of various kinds. Operations like disjoint union, the creation of new relations by means of quantifier-free formulas, and relabellings of relations make it possible to denote them using algebraic expressions. It is known that every monadic second-order property of a structure is verifiable in time proportional to the size of such an algebraic expression defining it. We prove here that this result remains true if we also use in these algebraic expressions a fusion operation that fuses all elements of the domain satisfying some unary predicate. The value mapping from these algebraic expressions to the structures they denote is a monadic second-order definable transduction, which means that the structure is definable inside the tree representing the algebraic expression by monadic second-order formulas. It follows (by using results of other articles) that, with this fusion operation, we cannot generate more graph families, but we can generate them with less unary auxiliary predicates. We also obtain clear-cut characterizations of Vertex Replacement and Hyperedge Replacement context-free graph grammars in terms of four types of operations, amongst which is the fusion of vertices satisfying a specified predicate.

In this paper we analyse the semantical definition of extensions for open default theories. We argue that this definition reflects the domain closure assumption and show how the domain closure assumption for countable and finite domains can be expressed in first-order default logic extended with the Carnap rule of inference. Also we give examples of the domain dependence of extensions for open default theories. In particular, we show that such extensions do not possess the minimality property.

Abstract Finitary sketches, i.e., sketches with finite-limit and finite-colimit specifications, are proved to be as strong as geometric sketches, i.e., sketches with finite-limit and arbitrary colimit specifications. Categories sketchable by such sketches are fully characterized in the infinitary first-order logic: they are axiomatizable by σ-coherent theories, i.e., basic theories using finite conjunctions, countable disjunctions, and finite quantifications. The latter result is absolute; the equivalence of geometric and finitary sketches requires (in fact, is equivalent to) the non-existence of measurable cardinals.

Abstract We investigate in this paper ‘natural’ distributions for the satisfiability problem (SAT) of prepositional logic, using concepts previously introduced by to study the average-case complexity of NP-complete problems. Gurevich showed that a problem with a flat distribution is not DistNP complete (for deterministic reductions), unless DEXPTIme ≠ NEXPTlme. We express the known results concerning fixed size and fixed density distributions for CNF in the framework of average-case complexity and show that all these distributions are flat. We introduce the family of symmetric distributions, which generalizes those mentioned before, and show that bounded symmetric distributions on ordered tuples of clauses (CNFTupIes) and on k-CNF (sets of k-literal-clauses), are flat. This eliminates all these distributions as candidates for ‘provably hard’ (i.e. DistNP complete) distributions for SAT, if one considers only deterministic reductions. Given the (presumed) naturalness and generality of these distributions, this result supports evidence that (at least polynomial-time, no-error) randomized reductions are appropriate in average-case complexity. We also observe, that there are non-flat distributions for which SAT is polynomial on the average, but that this is due to the particular choice of the size functions. Finally, Chváal and Szemerédi have shown that for certain fixed size distributions (which are also flat) resolution is exponential for almost all instances. We use this to show that every resolution algorithm will need at least exp(nα) (for any 0 ≤ α ≤ 1) time on the average. In other words, resolution-based algorithms will not establish that SAT, with these distributions, is in AverP.

In this paper a formal model of menus for interactive systems is defined. The definition of such a formal model is an important addition to the engineering concepts that are generally stressed in papers dealing with user interfaces. The paper takes the simple concept of a menu and defines a mathematical model which allows rigorous mathematical handling of the concepts of menus, menu items and menu constructs. Even for such a simple and well-known concept in user interfaces, such rigorous handling is missing in much of the literature concerning user interfaces. As shown in the paper, the mathematical modelling of menus, while mathematically simple, allows insights into menu definition. The formal model allows the definition of a new concept of completeness which describes some minimum basic requirements for any menu design language. Based on this definition it is shown that certain menu constructs discussed in the literature do not explicitly meet these basic requirements and therefore may have limited value as building blocks for menu design. The model also provides dialogue designers with well defined terminology which allows simple definitions of the terms persistent menus, transient menus and user context. It also combines the benefits of other menu definition languages in the literature and avoids their drawbacks. Finally, a menu design system based on these concepts is presented which allows easy definition of menu systems and their logic.

Relational schemas consisting of relation-schemes, key dependencies and key-based inclusion dependencies (referential integrity constraints) are considered. Schemas of this form are said to be entity-relationship (EER)-convertible if they can be associated with an EER schema. A procedure that determines whether a relational schema is EER-convertible is developed. A normal form is proposed for relational schemas representing EER object structures. For EER-convertible relational schemas, the corresponding normalization procedure is presented. The procedures can be used for analyzing the semantics of existing relational databases and for converting relational database schemas into object-oriented database schemas.>

Entity-relationship (ER) consistency is defined, and a complete set of incremental and reversible restructuring manipulations is proposed for ER-consistent relational schemas. It is shown how the schema restructuring manipulations that are proposed back both interactive and view-integration methodologies for schema design.>

Abstract We study the effects of Vopěnka's principle on properties of model theoretic logics. We show that Vopěnka's principle is equivalent to the assumption that every finitely generated logic has a compact cardinal. We show also that it is equivalent to the assumption that every such logic has a global Hanf number.

It is shown that the general inference problem for embedded implicational dependencies (EIDs) is undecidable. For the more important case of finite inference (i.e., inference for finite data bases), the problem is not even recursively enumerable (r.e.); rather, it is complete in co-r.e. These results hold even for typed EIDs without equality, as well as for (untyped) template dependencies. The case for typed template dependencies remains open. The complexity of the inference problem for full dependencies has also been characterized - it is complete in exponential time for full implicational dependencies, and even for full typed template dependencies.