Search Results

Documents authored by Knäuer, Simon

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2026.168
The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms

Authors: Manuel Bodirsky, Moritz Jahn, Simon Knäuer, Matěj Konečný, and Paul Winkler

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable [Hajnal Andréka and Roger D. Maddux, 1994]. Hirsch and Cristiani showed that the network satisfaction problem (NSP) for each of these algebras is in P or NP-hard [Matteo Cristiani and Robin Hirsch, 2004]. The literature contains many results on representations of relation algebras; in particular, some relation algebras with four atoms are not representable. We extend the result of Cristiani and Hirsch to relation algebras with at most 4 atoms: the NSP is always either in P or NP-hard. To this end, we construct universal, fully universal, or even normal representations for these algebras, whenever possible.
Cite as

Manuel Bodirsky, Moritz Jahn, Simon Knäuer, Matěj Konečný, and Paul Winkler. The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 168:1-168:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2026.168,
  author =	{Bodirsky, Manuel and Jahn, Moritz and Kn\"{a}uer, Simon and Kone\v{c}n\'{y}, Mat\v{e}j and Winkler, Paul},
  title =	{{The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{168:1--168:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.168},
  URN =		{urn:nbn:de:0030-drops-265564},
  doi =		{10.4230/LIPIcs.ICALP.2026.168},
  annote =	{Keywords: Constraint Satisfaction, Computational Complexity, Relation Algebras, Network Satisfaction, Normal Representations, Polynomial-Time Algorithms}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.116
Network Satisfaction Problems Solved by k-Consistency

Authors: Manuel Bodirsky and Simon Knäuer

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We show that the problem of deciding for a given finite relation algebra A whether the network satisfaction problem for A can be solved by the k-consistency procedure, for some k ∈ ℕ, is undecidable. For the important class of finite relation algebras A with a normal representation, however, the decidability of this problem remains open. We show that if A is symmetric and has a flexible atom, then the question whether NSP(A) can be solved by k-consistency, for some k ∈ ℕ, is decidable (even in polynomial time in the number of atoms of A). This result follows from a more general sufficient condition for the correctness of the k-consistency procedure for finite symmetric relation algebras. In our proof we make use of a result of Alexandr Kazda about finite binary conservative structures.
Cite as

Manuel Bodirsky and Simon Knäuer. Network Satisfaction Problems Solved by k-Consistency. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 116:1-116:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2023.116,
  author =	{Bodirsky, Manuel and Kn\"{a}uer, Simon},
  title =	{{Network Satisfaction Problems Solved by k-Consistency}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{116:1--116:20},
  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/entities/document/10.4230/LIPIcs.ICALP.2023.116},
  URN =		{urn:nbn:de:0030-drops-181680},
  doi =		{10.4230/LIPIcs.ICALP.2023.116},
  annote =	{Keywords: Constraint Satisfaction, Computational Complexity, Relation Algebras, Network Satisfaction, Qualitative Reasoning, k-Consistency, Datalog}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.120
Datalog-Expressibility for Monadic and Guarded Second-Order Logic

Authors: Manuel Bodirsky, Simon Knäuer, and Sebastian Rudolph

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also show that for every class C of finite structures that can be expressed in MSO and is closed under homomorphisms, and for all 𝓁,k ∈ , there exists a canonical Datalog program Π of width (𝓁,k), that is, a Datalog program of width (𝓁,k) which is sound for C (i.e., Π only derives the goal predicate on a finite structure 𝔄 if 𝔄 ∈ C) and with the property that Π derives the goal predicate whenever some Datalog program of width (𝓁,k) which is sound for C derives the goal predicate. The same characterisations also hold for Guarded Second-order Logic (GSO), which properly extends MSO. To prove our results, we show that every class C in GSO whose complement is closed under homomorphisms is a finite union of constraint satisfaction problems (CSPs) of ω-categorical structures.
Cite as

Manuel Bodirsky, Simon Knäuer, and Sebastian Rudolph. Datalog-Expressibility for Monadic and Guarded Second-Order Logic. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 120:1-120:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2021.120,
  author =	{Bodirsky, Manuel and Kn\"{a}uer, Simon and Rudolph, Sebastian},
  title =	{{Datalog-Expressibility for Monadic and Guarded Second-Order Logic}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{120:1--120:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.120},
  URN =		{urn:nbn:de:0030-drops-141897},
  doi =		{10.4230/LIPIcs.ICALP.2021.120},
  annote =	{Keywords: Monadic Second-order Logic, Guarded Second-order Logic, Datalog, constraint satisfaction, homomorphism-closed, conjunctive query, primitive positive formula, pebble game, \omega-categoricity}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact