Workshop on
Metafinite Model Theory and Definability and
Complexity of Numeric Graph Parameters
(Metafinite 2017)

Organizers

CONTACT: For further questions write to Dr. Elena Ravve at cselena@braude.ac.il

Background

• (A) Gurevich and Graedel in 1998 initiated the study of metafinite model theory to study descriptive complexity of numeric parameters. Metafinite model theory found most of its applications in databases and abstract state machines (ASM), but was not widely studied in connection to numeric combinatorial parameters.
• (B) Courcelle, Makowsky and Rotics initiated a definability theory for graph polynomials in 2000 and proved metatheorems for graph polynomials and numeric structural parameters.
• (C) Kotek, Makowsky and Ravve questioned wether the Turing model of computation was the right choice to discuss the complexity of numeric graph parameters and proposed alternatives using the Blum-Shub-Smale model of computation.
• (D) Nesetril and Ossona de Mendez introduced key notions in the theory of sparse graphs, such as graph families of bounded expansion or polynomial expansion and the (surprisingly robust) nowhere dense versus somewhere dense dichotomy. Their 2012 book 'Sparsity - Graphs, Structures, and Algorithms' combines model theory, analysis and combinatorics and gives a comprehensive overview. Recently Nesetril, along with Ossona de Mendez and Goodall, used finite model theory, and particularly interpretation schemes, to provide a general construction of polynomial graph invariants. This is an alternative approach to graph invariants related to the framework introduced by Makowsky and Zilber in 2005 and is best expressed in the framework of Metafinite model theory.

Program

Introductory Lectures (30 min)

1. J.A. Makowsky (Technion, Haifa) and E.V. Ravve (ORT-Braude, Karmiel), Generalized Chromatic Polynomials and the Counting Complexity for Metafinite Structures Abstract
2. A. Goodall (Charles University, Prague), Graph Polynomials by Interpreting Sequences of Finite Relational Structures Abstract

   Keynote Lectures (30 min)

3. E. Graedel (RWTH, Aachen), Metafinite Model Theory Abstract
4. Y. Gurevich (Microsoft, Redmond), Finite, Infinite and Metafinite Abstract
5. J. Nesetril (Charles University, Prague), Sparse Dense Dichotomy in the Context of Model Theory Abstract

   Contributed Lectures (30 min)

6. J. Hubicka (Charles University, Prague), Automorphism Groups and Ramsey Properties of Sparse Graphs Abstract
7. M. Kaminski (Oxford University, Oxford, GB), Decidable Classes of Datalog Programs with Arithmetic Abstract
8. T. Kotek (TU Vienna), Integer Sequences Arising from Graph Polynomials: An Application of a Theorem by C. Blatter and E. Specker Abstract
9. N. Labai (TU Vienna), On the Exact Learnabiliy of Numeric Graph Parameters. Abstract
10. A. Manuel (Chennai Mathematical Institute, Chennai) and T. Colcombet (Diderot University, Paris), Combinatorial Expressions and Inexpressability in Metafinite Structures. Abstract
11. K. Meer (BTU, Cottbus), Generalized Finite Automata over the Real Numbers. Abstract
12. E. Ternovska (SFU, Burnaby, BC), The Graedel-Gurevich Small Cost Condition and Capturing NP in Knowledge Representation Languages Abstract
13. M. Ziegler (KAIST, Daejeon), On the Consistency Problem for Modular Lattices and Related Structures. Abstract

    Finale (45 min)

14. Discussion and Problem Session