Document Open Access Logo

Non-Homogenizable Classes of Finite Structures

Authors Albert Atserias, Szymon Torunczyk

PDF
Thumbnail PDF

File

LIPIcs.CSL.2016.16.pdf
  • Filesize: 3.33 MB
  • 16 pages

Document Identifiers

Author Details

Albert Atserias
Szymon Torunczyk

Cite As Get BibTex

Albert Atserias and Szymon Torunczyk. Non-Homogenizable Classes of Finite Structures. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CSL.2016.16

Abstract

Homogenization is a powerful way of taming a class of finite structures with several interesting applications in different areas, from Ramsey theory in combinatorics to constraint satisfaction problems (CSPs) in computer science, through (finite) model theory.  A few sufficient conditions for a class of finite structures to allow homogenization are known, and here we provide a necessary condition. This lets us show that certain natural classes are not homogenizable: 1) the class of locally consistent systems of linear equations over the two-element field or any finite Abelian group, and 2) the class of finite structures that forbid homomorphisms from a specific MSO-definable class of structures of treewidth two. In combination with known results, the first example shows that, up to pp-interpretability, the CSPs that are solvable by local consistency methods are distinguished from the rest by the fact that their classes of locally consistent instances are homogenizable.  The second example shows that, for MSO-definable classes of forbidden patterns, treewidth one versus two is the dividing line to homogenizability.

Subject Classification

Keywords
  • Fraïssé class
  • amalgmation class
  • reduct
  • Constraint Satisfaction Problem
  • bounded width

Metrics

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

References

  1. A. Atserias, A. A. Bulatov, and A. Dawar. Affine systems of equations and counting infinitary logic. Theor. Comput. Sci., 410(18):1666-1683, 2009. Google Scholar
  2. A. Atserias and M. Weyer. Decidable relationships between consistency notions for constraint satisfaction problems. In Proceedings of the 23rd CSL International Conference and 18th EACSL Annual Conference on Computer Science Logic, CSL'09/EACSL'09, pages 102-116, Berlin, Heidelberg, 2009. Springer-Verlag. Google Scholar
  3. L. Barto. The constraint satisfaction problem and universal algebra. The Bulletin of Symbolic Logic, 21:319-337, 9 2015. Google Scholar
  4. L. Barto and M. Kozik. Constraint satisfaction problems solvable by local consistency methods. J. ACM, 61(1):3:1-3:19, January 2014. Google Scholar
  5. M. Bodirsky. Complexity of Constraints: An Overview of Current Research Themes, chapter Constraint Satisfaction Problems with Infinite Templates, pages 196-228. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. Google Scholar
  6. M. Bojańczyk, B. Klin, and S. Lasota. Automata theory in nominal sets. Logical Methods in Computer Science, 10(3:4):paper 4, 2014. Google Scholar
  7. M. Bojańczyk, L. Segoufin, and S. Toruńczyk. Verification of database-driven systems via amalgamation. In Richard Hull and Wenfei Fan, editors, Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22-27, 2013, pages 63-74. ACM, 2013. URL: http://dx.doi.org/10.1145/2463664.2465228.
  8. B. Courcelle and J. Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. Google Scholar
  9. J. Covington. Homogenizable relational structures. Illinois J. Math., 34(4):731-743, 12 1990. URL: http://projecteuclid.org/euclid.ijm/1255988065.
  10. P. L. Erdös, C. Tardif, and G. Tardos. On infinite-finite duality pairs of directed graphs. Order, 30(3):807-819, 2013. Google Scholar
  11. T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  12. Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, and Scott Weinstein. Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2007. Google Scholar
  13. W. Hodges. A Shorter Model Theory. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  14. J. Hubička and J. Nešetřil. Universal structures with forbidden homomorphisms. In Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics, pages 241-264. De Gruyter, 2015. Google Scholar
  15. Ph. G. Kolaitis, H. J. Proemel, and B. L. Rothschild. K_l+1-Free Graphs: Asymptotic Structure and a 0-1 Law. Transactions of the American Mathematical Society, 303(2):637-671, 1987. Google Scholar
  16. D. Macpherson. A survey of homogeneous structures. Discrete Mathematics, 311(15):1599-1634, 2011. Infinite Graphs: Introductions, Connections, Surveys. Google Scholar
  17. J. Nešetřil. Ramsey theory. In R. L. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics (Vol. 2), pages 1331-1403. MIT Press, Cambridge, MA, USA, 1995. 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