[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Document Open Access Logo

Advances in Algorithmic Meta Theorems (Invited Paper)

Authors Sebastian Siebertz , Alexandre Vigny

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2024.2.pdf
  • Filesize: 0.94 MB
  • 29 pages

Document Identifiers

Author Details

Sebastian Siebertz
  • University of Bremen, Germany
Alexandre Vigny
  • University Clermont Auvergne, France

Cite As Get BibTex

Sebastian Siebertz and Alexandre Vigny. Advances in Algorithmic Meta Theorems (Invited Paper). In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 2:1-2:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024) https://doi.org/10.4230/LIPIcs.FSTTCS.2024.2

Abstract

Tractability results for the model checking problem of logics yield powerful algorithmic meta theorems of the form:
Every computational problem expressible in a logic ℒ can be solved efficiently on every class C of structures satisfying certain conditions.
The most prominent logics studied in the field are (counting) monadic second-order logic (C)MSO and first-order logic FO and its extensions. The complexity of CMSO model checking in general and of FO model checking on monotone graph classes is very well understood. In recent years there has been a rapid and exciting development of new algorithmic meta theorems. On the one hand there has been major progress for FO model checking on hereditary graph classes. This progress was driven by the development of a combinatorial structure theory for the logically defined monadically stable and monadically dependent graph classes, as well as by the advent of the new width measure twinwidth. On the other hand new algorithmic meta theorems for new logics with expressive power between FO and CMSO offer a new unifying view on methods like the irrelevant vertex technique and recursive understanding. In this paper we overview the recent advances in algorithmic meta theorems and provide rough sketches for the methods to prove them.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Mathematics of computing → Graph theory
Keywords
  • Algorithmic meta theorems
  • monadic second-order logic
  • first-order logic
  • disjoint paths logic
  • algorithmic graph structure theory

Metrics

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

References

  1. Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322-330, 2014. URL: https://doi.org/10.1016/J.EJC.2013.06.048.
  2. Albert Atserias. E. grädel, p. kolaitis, l. libkin, m. marx, i. spencer, m. vardi, y. venema and s. weinstein , finite model theory and its applications, springer-verlag (2007). Comput. Sci. Rev., 2(1):55-59, 2008. URL: https://doi.org/10.1016/J.COSREV.2008.01.001.
  3. David A Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within nc1. Journal of Computer and System Sciences, 41(3):274-306, 1990. Google Scholar
  4. Michael Benedikt and H Jerome Keisler. Expressive power of unary counters. Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht, pages 34-50, 2005. Google Scholar
  5. Mikolaj Bojanczyk. Separator logic and star-free expressions for graphs. arXiv preprint, 2021. URL: https://arxiv.org/abs/2107.13953.
  6. Édouard Bonnet, Jan Dreier, Jakub Gajarskỳ, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, and Szymon Toruńczyk. Model checking on interpretations of classes of bounded local cliquewidth. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1-13, 2022. Google Scholar
  7. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1977-1996. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.118.
  8. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set, min dominating set, and coloring. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 35:1-35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPICS.ICALP.2021.35.
  9. Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Twin-width IV: ordered graphs and matrices. Journal of the ACM, 71(3):1-45, 2024. Google Scholar
  10. Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, and Stéphan Thomassé. Twin-width VI: the lens of contraction sequences. In SODA, pages 1036-1056. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.45.
  11. Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. Twin-width and polynomial kernels. Algorithmica, 84(11):3300-3337, 2022. URL: https://doi.org/10.1007/S00453-022-00965-5.
  12. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable fo model checking. ACM Journal of the ACM (JACM), 69(1):1-46, 2021. URL: https://doi.org/10.1145/3486655.
  13. Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. Decomposition horizons: from graph sparsity to model-theoretic dividing lines. arXiv preprint, 2022. URL: https://arxiv.org/abs/2209.11229.
  14. Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. Decomposition horizons and a characterization of stable hereditary classes of graphs. arXiv preprint, 2024. URL: https://arxiv.org/abs/2209.11229.
  15. Ashok Chandra and David Harel. Structure and complexity of relational queries. Journal of Computer and system Sciences, 25(1):99-128, 1982. URL: https://doi.org/10.1016/0022-0000(82)90012-5.
  16. Ashok K Chandra and Philip M Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 77-90, 1977. URL: https://doi.org/10.1145/800105.803397.
  17. Jianer Chen, Xiuzhen Huang, Iyad A Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences, 72(8):1346-1367, 2006. URL: https://doi.org/10.1016/J.JCSS.2006.04.007.
  18. Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michał Pilipczuk. Designing fpt algorithms for cut problems using randomized contractions. SIAM Journal on Computing, 45(4):1171-1229, 2016. URL: https://doi.org/10.1137/15M1032077.
  19. Edgar F Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377-387, 1970. URL: https://doi.org/10.1145/362384.362685.
  20. Thomas Colcombet. A combinatorial theorem for trees: applications to monadic logic and infinite structures. In Automata, Languages and Programming: 34th International Colloquium, ICALP 2007, Wrocław, Poland, July 9-13, 2007. Proceedings 34, pages 901-912. Springer, 2007. Google Scholar
  21. Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In Formal models and semantics, pages 193-242. Elsevier, 1990. URL: https://doi.org/10.1016/B978-0-444-88074-1.50010-X.
  22. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  23. Bruno Courcelle. The monadic second-order logic of graphs VII: Graphs as relational structures. Theoretical Computer Science, 101(1):3-33, 1992. URL: https://doi.org/10.1016/0304-3975(92)90148-9.
  24. Bruno Courcelle, Johann A Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150, 2000. URL: https://doi.org/10.1007/S002249910009.
  25. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1-3):77-114, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00184-5.
  26. Bruno Courcelle and Sang-il Oum. Vertex-minors, monadic second-order logic, and a conjecture by seese. Journal of Combinatorial Theory, Series B, 97(1):91-126, 2007. URL: https://doi.org/10.1016/J.JCTB.2006.04.003.
  27. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5(4). Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  28. Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, and Magnus Wahlström. Randomized contractions meet lean decompositions. ACM Transactions on Algorithms (TALG), 17(1):1-30, 2020. URL: https://doi.org/10.1145/3426738.
  29. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Minimum bisection is fixed parameter tractable. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 323-332, 2014. URL: https://doi.org/10.1145/2591796.2591852.
  30. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Minimum bisection is fixed-parameter tractable. SIAM Journal on Computing, 48(2):417-450, 2019. URL: https://doi.org/10.1137/140988553.
  31. Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In LICS 2007, pages 270-279. IEEE, 2007. URL: https://doi.org/10.1109/LICS.2007.31.
  32. John Doner. Tree acceptors and some of their applications. Journal of Computer and System Sciences, 4(5):406-451, 1970. URL: https://doi.org/10.1016/S0022-0000(70)80041-1.
  33. Rod G Downey and Michael R Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on computing, 24(4):873-921, 1995. URL: https://doi.org/10.1137/S0097539792228228.
  34. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0515-9.
  35. Rodney G Downey, Michael R Fellows, et al. Fundamentals of parameterized complexity, volume 4. Springer, 2013. Google Scholar
  36. Jan Dreier. Lacon-and shrub-decompositions: A new characterization of first-order transductions of bounded expansion classes. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470680.
  37. Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, and Szymon Toruńczyk. First-order model checking on monadically stable graph classes. arXiv preprint, 2023. URL: https://arxiv.org/abs/2311.18740.
  38. Jan Dreier, Jakub Gajarskỳ, Sandra Kiefer, Michał Pilipczuk, and Szymon Toruńczyk. Treelike decompositions for transductions of sparse graphs. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1-14, 2022. Google Scholar
  39. Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, and Alexandre Vigny. Combinatorial and algorithmic aspects of monadic stability. In 33rd International Symposium on Algorithms and Computation, ISAAC 2022, volume 248 of LIPIcs, pages 11:1-11:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPICS.ISAAC.2022.11.
  40. Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. First-order model checking on structurally sparse graph classes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 567-580, 2023. URL: https://doi.org/10.1145/3564246.3585186.
  41. Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and flatness in monadically stable and monadically nip classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2023. Google Scholar
  42. Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1550-1560, 2024. URL: https://doi.org/10.1145/3618260.3649739.
  43. Zdeněk Dvořák, Daniel Král, and Robin Thomas. Deciding first-order properties for sparse graphs. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 133-142. IEEE, 2010. Google Scholar
  44. Zdeněk Dvořák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM (JACM), 60(5):36, 2013. Google Scholar
  45. Heinz-Dieter Ebbinghaus and Jörg Flum. Finite model theory. Perspectives in Mathematical Logic. Springer, 1995. Google Scholar
  46. Heinz-Dieter Ebbinghaus, Jörg Flum, and Wolfgang Thomas. Mathematical logic (2. ed.). Undergraduate texts in mathematics. Springer, 1994. Google Scholar
  47. Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi, Stephan Kreutzer, Patrice Ossona De Mendez, Michał Pilipczuk, Daniel A Quiroz, Roman Rabinovich, and Sebastian Siebertz. Model-checking on ordered structures. ACM Transactions on Computational Logic (TOCL), 21(2):1-28, 2020. URL: https://doi.org/10.1145/3360011.
  48. Kousha Etessami. Counting quantifiers, successor relations, and logarithmic space. Journal of Computer and System Sciences, 54(3):400-411, 1997. URL: https://doi.org/10.1006/JCSS.1997.1485.
  49. Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of computation, 7:43-73, 1974. Google Scholar
  50. Ronald Fagin. Monadic generalized spectra. Math. Log. Q., 21(1):89-96, 1975. URL: https://doi.org/10.1002/MALQ.19750210112.
  51. Solomon Feferman and Robert L Vaught. The first order properties of products of algebraic systems. Journal of Symbolic Logic, 32(2), 1967. Google Scholar
  52. Jörg Flum and Martin Grohe. Fixed-parameter tractability, definability, and model-checking. SIAM Journal on Computing, 31(1):113-145, 2001. URL: https://doi.org/10.1137/S0097539799360768.
  53. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  54. Fedor V Fomin, Petr A Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M Thilikos. Compound logics for modification problems. ACM Transactions on Computational Logic, 2023. Google Scholar
  55. Fedor V Fomin, Petr A Golovach, Giannos Stamoulis, and Dimitrios M Thilikos. An algorithmic meta-theorem for graph modification to planarity and fol. ACM Transactions on Computation Theory, 14(3-4):1-29, 2023. URL: https://doi.org/10.1145/3571278.
  56. Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM (JACM), 48(6):1184-1206, 2001. URL: https://doi.org/10.1145/504794.504798.
  57. Jakub Gajarskỳ, Petr Hliněnỳ, Jan Obdržálek, Daniel Lokshtanov, and M Sridharan Ramanujan. A new perspective on fo model checking of dense graph classes. ACM Transactions on Computational Logic (TOCL), 21(4):1-23, 2020. URL: https://doi.org/10.1145/3383206.
  58. Jakub Gajarsky and Daniel Král'. Recovering sparse graphs. Leibniz International Proceedings in Informatics (LIPIcs), 117:29, 2018. Google Scholar
  59. Jakub Gajarskỳ, Stephan Kreutzer, Jaroslav Nešetřil, Patrice Ossona De Mendez, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic (TOCL), 21(4):1-41, 2020. URL: https://doi.org/10.1145/3382093.
  60. Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, and Szymon Torunczyk. Flipper games for monadically stable graph classes. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, volume 261 of LIPIcs, pages 128:1-128:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPICS.ICALP.2023.128.
  61. Jakub Gajarský, Michal Pilipczuk, Wojciech Przybyszewski, and Szymon Torunczyk. Twin-width and types. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, volume 229 of LIPIcs, pages 123:1-123:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPICS.ICALP.2022.123.
  62. Jakub Gajarskỳ, Michał Pilipczuk, and Szymon Toruńczyk. Stable graphs of bounded twin-width. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1-12, 2022. Google Scholar
  63. Robert Ganian, Petr Hliněnỳ, Alexander Langer, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar. Lower bounds on the complexity of mso1 model-checking. Journal of Computer and System Sciences, 80(1):180-194, 2014. URL: https://doi.org/10.1016/J.JCSS.2013.07.005.
  64. Robert Ganian, Petr Hliněnỳ, Jaroslav Nešetřil, Jan Obdržálek, and Patrice Ossona De Mendez. Shrub-depth: Capturing height of dense graphs. Logical Methods in Computer Science, 15, 2019. Google Scholar
  65. Robert Ganian, Petr Hliněnỳ, Jaroslav Nešetřil, Jan Obdržálek, Patrice Ossona de Mendez, and Reshma Ramadurai. When trees grow low: Shrubs and fast mso 1. In Mathematical Foundations of Computer Science 2012: 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings 37, pages 419-430. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-32589-2_38.
  66. Tobias Ganzow and Sasha Rubin. Order-invariant MSO is stronger than counting MSO in the finite. In Susanne Albers and Pascal Weil, editors, 25th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2008, volume 1 of LIPIcs, pages 313-324. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2008. URL: https://doi.org/10.4230/LIPICS.STACS.2008.1353.
  67. Petr A Golovach, Giannos Stamoulis, and Dimitrios M Thilikos. Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3684-3699. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.CH141.
  68. Erich Grädel, Phokion G Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y Vardi, Yde Venema, Scott Weinstein, et al. Finite Model Theory and its applications. Springer, 2007. Google Scholar
  69. Mario Grobler, Yiting Jiang, Patrice Ossona de Mendez, Sebastian Siebertz, and Alexandre Vigny. Discrepancy and sparsity. J. Comb. Theory B, 169:96-133, 2024. URL: https://doi.org/10.1016/J.JCTB.2024.06.001.
  70. Martin Grohe. Logic, graphs, and algorithms. Logic and automata, 2:357-422, 2008. Google Scholar
  71. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 479-488, 2011. URL: https://doi.org/10.1145/1993636.1993700.
  72. Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. AMS-ASL Joint Special Session, 558:181-206, 2009. Google Scholar
  73. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3):17:1-17:32, 2017. URL: https://doi.org/10.1145/3051095.
  74. Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 253-266, 2018. URL: https://doi.org/10.1145/3196959.3196970.
  75. Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 82-101, 2014. URL: https://doi.org/10.1137/1.9781611973402.7.
  76. Yuri Gurevich. Logic and the challenge of computer science. Technical report, University of Michigan, 1985. Google Scholar
  77. Wilfrid Hodges. Model theory, volume 42 of Encyclopedia of mathematics and its applications. Cambridge University Press, 1993. Google Scholar
  78. Neil Immerman. Upper and lower bounds for first order expressibility. Journal of Computer and System Sciences, 25(1):76-98, 1982. URL: https://doi.org/10.1016/0022-0000(82)90011-3.
  79. Neil Immerman. Languages that capture complexity classes. SIAM J. Comput., 16(4):760-778, 1987. URL: https://doi.org/10.1137/0216051.
  80. Neil Immerman. Descriptive complexity. Springer Science & Business Media, 1998. Google Scholar
  81. Yiting Jiang, Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. Regular partitions of gentle graphs. Acta Mathematica Hungarica, 161(2):719-755, 2020. Google Scholar
  82. Ken-ichi Kawarabayashi and Mikkel Thorup. The minimum k-way cut of bounded size is fixed-parameter tractable. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 160-169. IEEE, 2011. URL: https://doi.org/10.1109/FOCS.2011.53.
  83. Stephan Kreutzer. Algorithmic meta-theorems. Finite and algorithmic model theory, 379:177-270, 2011. Google Scholar
  84. Stephan Kreutzer. On the parameterized intractability of monadic second-order logic. Logical Methods in Computer Science, 8, 2012. URL: https://doi.org/10.2168/LMCS-8(1:27)2012.
  85. Stephan Kreutzer and Siamak Tazari. Lower bounds for the complexity of monadic second-order logic. In 2010 25th Annual IEEE Symposium on Logic in Computer Science, pages 189-198. IEEE, 2010. URL: https://doi.org/10.1109/LICS.2010.39.
  86. Stephan Kreutzer and Siamak Tazari. On brambles, grid-like minors, and parameterized intractability of monadic second-order logic. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 354-364. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.30.
  87. Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12. IEEE, 2017. URL: https://doi.org/10.1109/LICS.2017.8005133.
  88. Dietrich Kuske and Nicole Schweikardt. Gaifman normal forms for counting extensions of first-order logic. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  89. Leonid Libkin. Elements of finite model theory, volume 41. Springer, 2004. URL: https://doi.org/10.1007/978-3-662-07003-1.
  90. Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. URL: https://doi.org/10.1007/978-3-662-07003-1.
  91. Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Reducing CMSO model checking to highly connected graphs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107 of LIPIcs, pages 135:1-135:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPICS.ICALP.2018.135.
  92. Nikolas Mählmann. Monadically stable and monadically dependent graph classes: characterizations and algorithmic meta-theorems. PhD thesis, Universität Bremen, 2024. Google Scholar
  93. Johann A Makowsky and JP Marino. Tree-width and the monadic quantifier hierarchy. Theoretical computer science, 303(1):157-170, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00449-8.
  94. Maryanthe Malliaris and Saharon Shelah. Regularity lemmas for stable graphs. Transactions of the American Mathematical Society, 366(3):1551-1585, 2014. Google Scholar
  95. Jaroslav Nešetřil and P Ossona de Mendez. Structural sparsity. Russian Mathematical Surveys, 71(1):79, 2016. Google Scholar
  96. Jaroslav Nešetřil and Patrice Ossona De Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. URL: https://doi.org/10.1016/J.EJC.2011.01.006.
  97. Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014-2033. SIAM, 2021. Google Scholar
  98. Jaroslav Nešetřil, Roman Rabinovich, Patrice Ossona de Mendez, and Sebastian Siebertz. Linear rankwidth meets stability. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1180-1199. SIAM, 2020. Google Scholar
  99. Pierre Ohlmann, Michał Pilipczul, Szymon Toruńczyk, and Wojciech Przybyszewski. Canonical decompositions in monadically stable and bounded shrubdepth graph classes. arXiv preprint, 2023. URL: https://arxiv.org/abs/2303.01473.
  100. Open problems from the workshop on algorithms, logic and structure, university of warwick, 2016. URL: https://warwick.ac.uk/fac/sci/maths/people/staff/daniel_kral/alglogstr/openproblems.pdf.
  101. Sang-il Oum and Paul Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514-528, 2006. URL: https://doi.org/10.1016/J.JCTB.2005.10.006.
  102. Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, and Alexandre Vigny. Algorithms and data structures for first-order logic with connectivity under vertex failures. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, volume 229 of LIPIcs, pages 102:1-102:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPICS.ICALP.2022.102.
  103. Neil Robertson and Paul D Seymour. Graph minors I - XXIII, 1983 - 2010. Google Scholar
  104. Neil Robertson and Paul D Seymour. Graph minors. V. excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92-114, 1986. URL: https://doi.org/10.1016/0095-8956(86)90030-4.
  105. Neil Robertson and Paul D Seymour. Graph minors. XIII. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/JCTB.1995.1006.
  106. Ignasi Sau, Giannos Stamoulis, and Dimitrios M Thilikos. A more accurate view of the flat wall theorem. Journal of Graph Theory, 107(2):263-297, 2024. Google Scholar
  107. Ignasi Sau, Giannos Stamoulis, and Dimitrios M Thilikos. Parameterizing the quantification of cmso: model checking on minor-closed graph classes. arXiv preprint arXiv:2406.18465, 2024. URL: https://doi.org/10.48550/arXiv.2406.18465.
  108. Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M Thilikos, and Alexandre Vigny. Model checking disjoint-paths logic on topological-minor-free graph classes. In Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1-12, 2024. URL: https://doi.org/10.1145/3661814.3662089.
  109. Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny. First-order logic with connectivity operators. ACM Transactions on Computational Logic, 24(4):1-23, 2023. URL: https://doi.org/10.1145/3595922.
  110. Nicole Schweikardt. Arithmetic, first-order logic, and counting quantifiers. ACM Transactions on Computational Logic (TOCL), 6(3):634-671, 2005. URL: https://doi.org/10.1145/1071596.1071602.
  111. Detlef Seese. The structure of the models of decidable monadic theories of graphs. Annals of pure and applied logic, 53(2):169-195, 1991. URL: https://doi.org/10.1016/0168-0072(91)90054-P.
  112. Detlef Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6(6):505-526, 1996. URL: https://doi.org/10.1017/S0960129500070079.
  113. Saharon Shelah. Classification theory: and the number of non-isomorphic models. Elsevier, 1990. Google Scholar
  114. Larry J Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1-22, 1976. URL: https://doi.org/10.1016/0304-3975(76)90061-X.
  115. Larry Joseph Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, Massachusetts Institute of Technology, 1974. Google Scholar
  116. James W. Thatcher and Jesse B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical systems theory, 2(1):57-81, 1968. URL: https://doi.org/10.1007/BF01691346.
  117. Dimitrios M Thilikos and Sebastian Wiederrecht. Excluding surfaces as minors in graphs. arXiv preprint, 2023. URL: https://arxiv.org/abs/2306.01724.
  118. Szymon Toruńczyk. Aggregate queries on sparse databases. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 427-443, 2020. Google Scholar
  119. Szymon Toruńczyk. Flip-width: Cops and robber on dense graphs. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 663-700. IEEE, 2023. Google Scholar
  120. Moshe Y Vardi. The complexity of relational query languages. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 137-146, 1982. Google Scholar
  121. Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete Mathematics, 309(18):5562-5568, 2009. URL: https://doi.org/10.1016/J.DISC.2008.03.024.
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