Document Open Access Logo

Structural Properties of the First-Order Transduction Quasiorder

Authors Jaroslav Nešetřil , Patrice Ossona de Mendez , Sebastian Siebertz

PDF
Thumbnail PDF

File

LIPIcs.CSL.2022.31.pdf
  • Filesize: 1.08 MB
  • 16 pages

Document Identifiers

Author Details

Jaroslav Nešetřil
  • Computer Science Institute, Charles University (IUUK), Prague, Czech Republic
Patrice Ossona de Mendez
  • Centre d'Analyse et de Mathématiques Sociales (CNRS, UMR 8557), Paris, France
  • Computer Science Institute, Charles University, Prague, Czech Republic
Sebastian Siebertz
  • University of Bremen, Germany

Funding

This paper is part of a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 810115 - Dynasnet) and from the German Research Foundation (DFG) with grant agreement No 444419611.

Cite As Get BibTex

Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. Structural Properties of the First-Order Transduction Quasiorder. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CSL.2022.31

Abstract

Logical transductions provide a very useful tool to encode classes of structures inside other classes of structures. In this paper we study first-order (FO) transductions and the quasiorder they induce on infinite classes of finite graphs. Surprisingly, this quasiorder is very complex, though shaped by the locality properties of first-order logic. This contrasts with the conjectured simplicity of the monadic second order (MSO) transduction quasiorder. We first establish a local normal form for FO transductions, which is of independent interest. Then we prove that the quotient partial order is a bounded distributive join-semilattice, and that the subposet of additive classes is also a bounded distributive join-semilattice. The FO transduction quasiorder has a great expressive power, and many well studied class properties can be defined using it. We apply these structural properties to prove, among other results, that FO transductions of the class of paths are exactly perturbations of classes with bounded bandwidth, that the local variants of monadic stability and monadic dependence are equivalent to their (standard) non-local versions, and that the classes with pathwidth at most k, for k ≥ 1 form a strict hierarchy in the FO transduction quasiorder.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Mathematics of computing → Graph theory
Keywords
  • Finite model theory
  • first-order transductions
  • structural graph theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. J. T. Baldwin and S. Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26(3):229-303, 1985. Google Scholar
  2. A. Blumensath and B. Courcelle. On the monadic second-order transduction hierarchy. Logical Methods in Computer Science, 6(2), 2010. URL: https://doi.org/10.2168/LMCS-6(2:2)2010.
  3. T. Colcombet. A combinatorial theorem for trees. In International Colloquium on Automata, Languages, and Programming, pages 901-912. Springer, 2007. Google Scholar
  4. B. Courcelle and S. Oum. Vertex-minors, monadic second-order logic, and a conjecture by seese. Journal of Combinatorial Theory, Series B, 97(1):91-126, 2007. Google Scholar
  5. R. Diestel. Graph theory, volume 173 of. Graduate texts in mathematics, page 7, 2012. Google Scholar
  6. H. Gaifman. On local and non-local properties. Studies in Logic and the Foundations of Mathematics, 107:105-135, 1982. Google Scholar
  7. J. Gajarský, S. Kreutzer, J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, S. Siebertz, and S. Toruńczyk. First-order interpretations of bounded expansion classes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 126:1-126:14, 2018. Google Scholar
  8. R. Ganian, P. Hliněný, J. Nešetřil, J. Obdržálek, and P. Ossona de Mendez. Shrub-depth: Capturing height of dense graphs. Logical Methods in Computer Science, 15(1), 2019. Google Scholar
  9. R. Ganian, P. Hliněný, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez, and R. Ramadurai. When trees grow low: Shrubs and fast MSO₁. In International Symposium on Mathematical Foundations of Computer Science, volume 7464 of Lecture Notes in Computer Science, pages 419-430. Springer-Verlag, 2012. Google Scholar
  10. W. Hodges. Model theory, volume 42. Cambridge University Press, 1993. Google Scholar
  11. O. Kwon, R. McCarty, S. Oum, and P. Wollan. Obstructions for bounded shrub-depth and rank-depth. CoRR, abs/1911.00230, 2019. URL: http://arxiv.org/abs/1911.00230.
  12. V. V. Lozin. From tree-width to clique-width: Excluding a unit interval graph. In Seok-Hee Hong, Hiroshi Nagamochi, and Takuro Fukunaga, editors, Algorithms and Computation, pages 871-882, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  13. J. Nešetřil and P. Ossona de Mendez. Cluster analysis of local convergent sequences of structures. Random Structures & Algorithms, 51(4):674-728, 2017. Google Scholar
  14. J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Rankwidth meets stability. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014-2033, 2021. URL: https://doi.org/10.1137/1.9781611976465.120.
  15. J. Nešetřil, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. Linear rankwidth meets stability. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 1180-1199, 2020. Google Scholar
  16. J. Nešetřil, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. Classes of graphs with low complexity: The case of classes with bounded linear rankwidth. European Journal of Combinatorics, 91:103223, 2021. Special issue dedicated to Xuding Zhu’s 60th birthday. URL: https://doi.org/10.1016/j.ejc.2020.103223.
  17. J. Nešetřil, P. Ossona de Mendez, and S. Siebertz. Structural properties of the first-order transduction quasiorder, 2021. URL: http://arxiv.org/abs/2010.02607.
  18. D. Seese. The structure of the models of decidable monadic theories of graphs. Annals of pure and applied logic, 53(2):169-195, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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