Metafinite Model Theory and Definability and
Complexity of Numeric Graph Parameters
(Metafinite 2017)Affiliated with LICS 2017
June 19 2017 in room M109, Reykjavik, Iceland
Go to http://cs.technion.ac.il/~janos/metafinite2017
or Go to http://cs.technion.ac.il/~janos/metafinite-talks/talks.html
Schedule of talks
A. Goodall (Charles University, Prague), J.A. Makowsky (Technion, Haifa), E.V. Ravve (ORT-Braude, Karmiel)
CONTACT: For further questions write to Dr. Elena Ravve at email@example.com
The workshop will bring together three strands of investigation dealing with the model theory and complexity of numeric graph parameters and their generalization to other first order structures.
- (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.
The aim of the workshop is to bring together researchers of these four strands in order to further explore and elaborate on the appropriate framework for the study of numeric structural parameters and polynomials and to investigate further metatheorems.
The list below is not the chronological order.
Introductory Lectures (40 min)
- J.A. Makowsky (Technion, Haifa), Generalized Chromatic Polynomials and the Counting Complexity for Metafinite Structures Abstract
- A. Goodall (Charles University, Prague), Graph Polynomials by Interpreting Sequences of Finite Relational Structures Abstract
Keynote Lectures (40 min)
- E. Graedel (RWTH, Aachen), Metafinite Model Theory Abstract
- Y. Gurevich (Microsoft, Redmond), Finite, Infinite and Metafinite Abstract
- J. Nesetril (Charles University, Prague), Sparse Dense Dichotomy in the Context of Model Theory Abstract
Contributed Lectures (30 min)
- J. Hubicka (Charles University, Prague), Automorphism Groups and Ramsey Properties of Sparse Graphs Abstract
- M. Kaminski (Oxford University, Oxford, GB), Decidable Classes of Datalog Programs with Arithmetic Abstract
- T. Kotek (TU Vienna), Integer Sequences Arising from Graph Polynomials: An Application of a Theorem by C. Blatter and E. Specker Abstract
- N. Labai (TU Vienna), On the Exact Learnabiliy of Numeric Graph Parameters. Abstract
- A. Manuel (Chennai Mathematical Institute, Chennai), Combinatorial Expressions and Inexpressability in Metafinite Structures. Abstract
- K. Meer (BTU, Cottbus), Generalized Finite Automata over the Real Numbers. Abstract
- E. Ternovska (SFU, Burnaby, BC), The Graedel-Gurevich Small Cost Condition and Capturing NP in Knowledge Representation Languages Abstract
- M. Ziegler (KAIST, Daejeon), On the Consistency Problem for Modular Lattices and Related Structures. Abstract
Finale (45 min)
- Discussion and Problem Session