19 Jun 2017
Reykjavik, Iceland
Second Call for Presentations (Extended deadline)
Workshop on
Metafinite model theory and definability and
complexity of numeric graph parameters
(Metafinite 2017)
Affiliated with LICS 2017
June 19 2017, Reykjavik, Iceland
http://cs.technion.ac.il/~janos/metafinte2017
AIM:
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.
For more background see
http://cs.technion.ac.il/~janos/metafinte2017
ORGANIZERS and PC:
A. Goodall (Charles University, Prague)
J.A. Makowsky (Technion, Haifa)
E.V. Ravve (ORT-Braude, Karmiel)
KEYNOTE SPEAKERS: (* still to be confirmed)
Y. Gurevich (Microsoft, Redmond)
E. Graedel (RWTH, Aachen)
J. Nesetril (Charles University, Prague)
CONFIRMED SPEAKERS:
K. Meer (BTU, Cottbus)
M. Ziegler (KAIST, Southkorea)
T. Kotek (TU, Vienna)
N. Labai (TU, Vienna)
A. Manuel (CMI, Chennai)
T. Colcombet (Paris VII, Paris)
J. Hubicka* (Charles University, Prague)
Introductory lecture will be given by the organizers.
SUBMISSION:
Proposal for 30 minutes talk are sollicited in the form of an abstract
of up to 4 pages in pdf-format.
This may include already published material relevant for the workshop,
original contributions, as well as work in progress.
Submissions are for talks, not for papers.
There will be no formal proceedings.
Hence submissions should have a single author who is the speaker.
The abstract may include a list of coauthors.
Proposals for presentation should be sent to
cselena@braude.ac.il
with subject: Metafinite 2017
PUBLICATION:
Accepted presentations will be posted on the workshop homepage.
It is planned to publish a special issue
in a suitable journal, based on the accepted presentations.
The special issue is meant to focus on Metafinite Model Theory
and its applications.
IMPORTANT DATES (AoE):
* Submission: Friday 18 April 2017
* Notification: Monday 1 May 2017
* Final version: Monday 15 May 2017
* Workshop: Monday June 19 2017
CONTACT: For further questions write to Dr. Elena Ravve at
cselena@braude.ac.il
--
[LOGIC] mailing list
http://www.dvmlg.de/mailingliste.html
Archive: http://www.illc.uva.nl/LogicList/
provided by a collaboration of the DVMLG, the Maths Departments in Bonn and Hamburg, and the ILLC at the Universiteit van Amsterdam