Metafinite Model Theory and Definability and Complexity of Numeric Graph Parameters. Affiliated with the ACM/IEEE Symposium on Logic in Computer Science (LICS)
Háskólinn í Reykjavík

Metafinite Model Theory and Definability and Complexity of Numeric Graph Parameters. Affiliated with the ACM/IEEE Symposium on Logic in Computer Science (LICS)

Workshop on 
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 
or Go to

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


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

19. jún. 2017 kl. 08:00
Viðburði er lokið

Háskólinn í Reykjavík

Menntavegi 1, 101 Reykjavík

+354 599 6200

Vefsíða viðburðar

Heimasíða staðar