Call for participation (May 5, 2017)

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

Affiliated with LICS 2017
June 19 2017, Reykjavik, Iceland
Go to
or Go to

Schedule of talks

Location: M1.09, see also


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. 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)

  1. J.A. Makowsky (Technion, Haifa), 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 (40 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), 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