License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.119
URN: urn:nbn:de:0030-drops-181712
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18171/
Go to the corresponding LIPIcs Volume Portal

Braunfeld, Samuel ; Dawar, Anuj ; Eleftheriadis, Ioannis ; Papadopoulos, Aris

Monadic NIP in Monotone Classes of Relational Structures

pdf-format:
LIPIcs-ICALP-2023-119.pdf (0.8 MB)

Abstract

We prove that for any monotone class of finite relational structures, the first-order theory of the class is NIP in the sense of stability theory if, and only if, the collection of Gaifman graphs of structures in this class is nowhere dense. This generalises results previously known for graphs to relational structures and answers an open question posed by Adler and Adler (2014). The result is established by the application of Ramsey-theoretic techniques and shows that the property of being NIP is highly robust for monotone classes. We also show that the model-checking problem for first-order logic is intractable on any monotone class of structures that is not (monadically) NIP. This is a contribution towards the conjecture that the hereditary classes of structures admitting fixed-parameter tractable model-checking are precisely those that are monadically NIP.

BibTeX - Entry

@InProceedings{braunfeld_et_al:LIPIcs.ICALP.2023.119,
  author =	{Braunfeld, Samuel and Dawar, Anuj and Eleftheriadis, Ioannis and Papadopoulos, Aris},
  title =	{{Monadic NIP in Monotone Classes of Relational Structures}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{119:1--119:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18171},
  URN =		{urn:nbn:de:0030-drops-181712},
  doi =		{10.4230/LIPIcs.ICALP.2023.119},
  annote =	{Keywords: Model theory, finite model theory, structural graph theory, model-checking}
}

Keywords: Model theory, finite model theory, structural graph theory, model-checking
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI