Document Open Access Logo

Preservation Theorems Through the Lens of Topology

Author Aliaume Lopez

PDF
Thumbnail PDF

File

LIPIcs.CSL.2021.32.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Aliaume Lopez
  • Université Paris-Saclay, ENS Paris-Saclay, CNRS, LSV, Gif-sur-Yvette, France

Acknowledgements

I thank Jean Goubault-Larrecq and Sylvain Schmitz for their help and support in writing this paper.

Cite AsGet BibTex

Aliaume Lopez. Preservation Theorems Through the Lens of Topology. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CSL.2021.32

Abstract

In this paper, we introduce a family of topological spaces that captures the existence of preservation theorems. The structure of those spaces allows us to study the relativisation of preservation theorems under suitable definitions of surjective morphisms, subclasses, sums, products, topological closures, and projective limits. Throughout the paper, we also integrate already known results into this new framework and show how it captures the essence of their proofs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Mathematics of computing → Discrete mathematics
  • Mathematics of computing → Point-set topology
Keywords
  • Preservation theorem
  • Pre-spectral space
  • Noetherian space
  • Spectral space

Metrics

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

Related Versions

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
  2. Miklós Ajtai and Yuri Gurevich. Monotone versus positive. Journal of the ACM, 34(4):1004-1015, 1987. URL: https://doi.org/10.1145/31846.31852.
  3. Miklós Ajtai and Yuri Gurevich. Datalog vs first-order logic. Journal of Computer and System Sciences, 49(3):562-588, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80071-6.
  4. Albert Atserias, Anuj Dawar, and Martin Grohe. Preservation under extensions on well-behaved finite structures. SIAM Journal on Computing, 38(4):1364-1381, 2008. URL: https://doi.org/10.1137/060658709.
  5. Albert Atserias, Anuj Dawar, and Phokion G. Kolaitis. On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM, 53(2):208-237, 2006. URL: https://doi.org/10.1145/1131342.1131344.
  6. Chen Chung Chang and H. Jerome Keisler. Model Theory, volume 73 of Studies in Logic and the Foundations of Mathematics. Elsevier, 1990. Google Scholar
  7. Yijia Chen and Jörg Flum. Forbidden induced subgraphs and the Łoś-Tarski Theorem. Preprint, 2020. URL: https://arxiv.org/abs/2008.00420.
  8. Bruno Courcelle. Monadic second-order definable graph transductions: a survey. Theoretical Computer Science, 126(1):53-75, 1994. URL: https://doi.org/10.1016/0304-3975(94)90268-2.
  9. Anuj Dawar. Homomorphism preservation on quasi-wide classes. Journal of Computer and System Sciences, 76(5):324-332, 2010. URL: https://doi.org/10.1016/j.jcss.2009.10.005.
  10. Anuj Dawar and Stephan Kreutzer. On Datalog vs. LFP. In Proceedings of ICALP'08, volume 5126 of Lecture Notes in Computer Science, pages 160-171, 2008. URL: https://doi.org/10.1007/978-3-540-70583-3_14.
  11. Anuj Dawar and Abhisekh Sankaran. Extension preservation in the finite and prefix classes of first order logic. Preprint, 2020. URL: https://arxiv.org/abs/2007.05459.
  12. Alin Deutsch, Alan Nash, and Jeffrey B. Remmel. The chase revisited. In Proceedings of PODS'08, pages 149-158, 2008. URL: https://doi.org/10.1145/1376916.1376938.
  13. Max Dickmann, Niels Schwartz, and Marcus Tressl. Spectral Spaces, volume 35 of New Mathematical Monographs. Cambridge University Press, 2019. Google Scholar
  14. Guoli Ding. Subgraphs and well-quasi-ordering. Journal of Graph Theory, 16:489-502, 1992. URL: https://doi.org/10.1002/jgt.3190160509.
  15. Tomás Feder and Moshe Y. Vardi. Homomorphism closed vs. existential positive. In Proceedings of LICS'03, pages 311-320, 2003. URL: https://doi.org/10.1109/LICS.2003.1210071.
  16. Solomon Feferman and Robert Vaught. The first order properties of products of algebraic systems. Fundamenta Mathematicae, 47(1):57-103, 1959. URL: https://doi.org/10.4064/fm-47-1-57-103.
  17. Diego Figueira and Leonid Libkin. Pattern logics and auxiliary relations. In Proceedings of CSL-LICS'14, pages 40:1-40:10, 2014. URL: https://doi.org/10.1145/2603088.2603136.
  18. Amélie Gheerbrant, Leonid Libkin, and Cristina Sirangelo. Naïve evaluation of queries over incomplete databases. ACM Transactions on Database Systems, 39(4):1-42, 2014. URL: https://doi.org/10.1145/2691190.2691194.
  19. Jean Goubault-Larrecq. Non-Hausdorff Topology and Domain Theory, volume 22 of New Mathematical Monographs. Cambridge University Press, 2013. Google Scholar
  20. Martin Grohe. Existential least fixed-point logic and its relatives. Journal of Logic and Computation, 7(2):205-228, 1997. URL: https://doi.org/10.1093/logcom/7.2.205.
  21. Yuri Gurevich. Toward logic tailored for computational complexity. In Computation and Proof Theory, Proceedings of LC'84, volume 1104 of Lecture Notes in Mathematics, pages 175-216. Springer, 1984. URL: https://doi.org/10.1007/BFb0099486.
  22. Frederik Harwath, Lucas Heimberg, and Nicole Schweikardt. Preservation and decomposition theorems for bounded degree structures. In Proceedings of CSL-LICS'14, pages 49:1-49:10, 2014. URL: https://doi.org/10.1145/2603088.2603130.
  23. Melvin Hochster. Prime ideal structure in commutative rings. Transactions of the American Mathematical Society, 142:43-60, 1969. URL: https://doi.org/10.1090/S0002-9947-1969-0251026-X.
  24. Wilfrid Hodges. A shorter model theory. Cambridge University Press, 1997. Google Scholar
  25. Phokion G. Kolaitis. Reflections on finite model theory. In Proceedings of LICS'07, pages 257-269, 2007. URL: https://doi.org/10.1109/LICS.2007.39.
  26. Joseph B. Kruskal. The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combinatorial Theory, Series A, 13(3):297-305, 1972. URL: https://doi.org/10.1016/0097-3165(72)90063-5.
  27. Leonid Libkin. Elements of finite model theory. Springer, 2012. Google Scholar
  28. Jerzy Łoś. On the extending of models (I). Fundamenta Mathematicae, 42(1):38-54, 1955. URL: https://doi.org/10.4064/fm-42-1-38-54.
  29. Johann A. Makowsky. Algorithmic uses of the Feferman-Vaught Theorem. Annals of Pure and Applied Logic, 126(1-3):159-213, 2004. URL: https://doi.org/10.1016/j.apal.2003.11.002.
  30. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. Springer, 2012. Google Scholar
  31. Eric Rosen. Some aspects of model theory and finite structures. Bulletin of Symbolic Logic, 8(3):380-403, 2002. URL: https://doi.org/10.2178/bsl/1182353894.
  32. Benjamin Rossman. Homomorphism preservation theorems. Journal of the ACM, 55(3):15:1-15:53, 2008. URL: https://doi.org/10.1145/1379759.1379763.
  33. Benjamin Rossman. An improved homomorphism preservation theorem from lower bounds in circuit complexity. ACM SIGLOG News, 3(4):33-46, 2016. URL: https://doi.org/10.1145/3026744.3026746.
  34. Alexei P. Stolboushkin. Finitely monotone properties. In Proceedings of LICS'95, pages 324-330, 1995. URL: https://doi.org/10.1109/LICS.1995.523267.
  35. Arthur H. Stone. Inverse limits of compact spaces. General Topology and its Applications, 10(2):203-211, 1979. URL: https://doi.org/10.1016/0016-660X(79)90008-4.
  36. William W. Tait. A counterexample to a conjecture of Scott and Suppes. Journal of Symbolic Logic, 24(1):15-16, 1959. URL: https://doi.org/10.2307/2964569.
  37. Alfred Tarski. Contributions to the theory of models. I. Indagationes Mathematicae (Proceedings), 57:572-581, 1954. URL: https://doi.org/10.1016/S1385-7258(54)50074-0.
  38. Balder ten Cate and Phokion G. Kolaitis. Structural characterizations of schema-mapping languages. In Proceedings of ICDT'09, pages 63-72, 2009. URL: https://doi.org/10.1145/1514894.1514903.
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 Imprint Privacy Contact