Document Open Access Logo

A Finitary Analogue of the Downward Löwenheim-Skolem Property

Author Abhisekh Sankaran

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.37.pdf
  • Filesize: 0.63 MB
  • 21 pages

Document Identifiers

Author Details

Abhisekh Sankaran

Cite As Get BibTex

Abhisekh Sankaran. A Finitary Analogue of the Downward Löwenheim-Skolem Property. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 37:1-37:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CSL.2017.37

Abstract

We present a model-theoretic property of finite structures, that can be seen to be a finitary analogue of the well-studied downward Löwenheim-Skolem property from classical model theory. We call this property the *L-equivalent bounded substructure property*, denoted L-EBSP, where L is either FO or MSO. Intuitively, L-EBSP states that a large finite structure contains a small "logically similar" substructure, where logical similarity means indistinguishability with respect to sentences of L having a given quantifier nesting depth. It turns out that this simply stated property is enjoyed by a variety of classes of interest in computer science: examples include regular languages of words, trees (unordered, ordered or ranked) and nested words, and various classes of graphs, such as cographs, graph classes of bounded tree-depth, those of bounded shrub-depth and n-partite cographs. Further, L-EBSP remains preserved in the classes generated from the above by operations that are implementable using quantifier-free translation schemes. All of the aforementioned classes admit natural tree representations for their structures. We use this fact to show that the small and logically similar substructure of a large structure in any of these classes, can be computed in time linear in the size of the tree representation of the structure, giving linear time fixed parameter tractable (f.p.t.) algorithms for checking L-definable properties of the large structure. We conclude by presenting a strengthening of L-EBSP, that asserts "logical self-similarity at all scales" for a suitable notion of scale. We call this the *logical fractal* property and show that most of the classes mentioned above are indeed, logical fractals.

Subject Classification

Keywords
  • downward Lowenheim-Skolem theorem
  • trees
  • nested words
  • tree-depth
  • cographs
  • tree representation
  • translation schemes
  • composition lemma
  • f.p.t.
  • log

Metrics

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

References

  1. Natasha Alechina and Yuri Gurevich. Syntax vs. semantics on finite structures. In Structures in Logic and Computer Science. A Selection of Essays in Honor of A. Ehrenfeucht, pages 14-33. Springer-Verlag, 1997. Google Scholar
  2. Rajeev Alur and Parthasarathy Madhusudan. Adding nesting structure to words. J. ACM, 56(3), 2009. Google Scholar
  3. Albert Atserias, Anuj Dawar, and Martin Grohe. Preservation under extensions on well-behaved finite structures. SIAM J. Comput., 38(4):1364-1381, 2008. URL: http://dx.doi.org/10.1137/060658709.
  4. Michael Barnsley. Fractals Everywhere. Academic Press Professional, Inc., 1988. Google Scholar
  5. Hubert Comon, Max Dauchet, Remi Gilleron, Christof Löding, Florent Jacquemard, Denis Lugiez, Sophie Tison, and Marc Tommasi. Tree automata techniques and applications, 2007. release October 12, 2007. URL: http://www.grappa.univ-lille3.fr/tata.
  6. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  7. 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. Google Scholar
  8. Michael Elberfeld, Martin Grohe, and Till Tantau. Where first-order and monadic second-order logic coincide. In LICS 2012, Croatia, June 25-28, 2012, pages 265-274, 2012. Google Scholar
  9. Solomon Feferman and Robert Vaught. The first order properties of products of algebraic systems. Fundamenta Mathematicae, 47(1):57-103, 1959. Google Scholar
  10. Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic, 130(1-3):3-31, 2004. Google Scholar
  11. Jakub Gajarsky and Petr Hlinený. Kernelizing MSO properties of trees of fixed height, and some consequences. Log. Meth. Comp. Sci., 11(19):1-26, 2015. Google Scholar
  12. Robert Ganian, Petr Hlinený, Jaroslav Nešetřil, Jan Obdrzálek, Patrice Ossona de Mendez, and Reshma Ramadurai. When trees grow low: Shrubs and fast MSO1. In MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, pages 419-430, 2012. Google Scholar
  13. Martin Grohe. Some remarks on finite Löwenheim-Skolem theorems. Math. Log. Q., 42:569-571, 1996. Google Scholar
  14. Martin Grohe. Logic, graphs, and algorithms. Logic and automata, 2:357-422, 2008. Google Scholar
  15. Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. Model Theoretic Methods in Finite Combinatorics, 558:181-206, 2011. Google Scholar
  16. Yuri Gurevich. Toward logic tailored for computational complexity. In Michael M. Richter et al., editor, Computation and Proof Theory: Proceedings of the Logic Colloquium held in Aachen, July 18-23, 1983, Part II, pages 175-216. Springer-Verlag, 1984. Google Scholar
  17. Frederik Harwath, Lucas Heimberg, and Nicole Schweikardt. Preservation and decomposition theorems for bounded degree structures. Log. Meth. Comp. Sci., 11(4), 2015. Google Scholar
  18. Beverly Jamison and Stephan Olariu. Recognizing P₄-sparse graphs in linear time. SIAM Journal on Computing, 21(2):381-406, 1992. Google Scholar
  19. Beverly Jamison and Stephan Olariu. Linear time optimization algorithms for P₄-sparse graphs. Discrete Applied Mathematics, 61(2):155-175, 1995. Google Scholar
  20. Leonid Libkin. Elements of Finite Model Theory. Springer-Verlag, 2004. Google Scholar
  21. Per Lindström. A characterization of elementary logic. In Sören Halldén, editor, Modality, Morality and Other Problems of Sense and Nonsense, pages 189-191. Lund,Gleerup, 1973. Google Scholar
  22. Leopold Löwenheim. Über möglichkeiten im relativkalkül. Mathematische Annalen, 76(4):447-470, 1915. Google Scholar
  23. Johann A. Makowsky. Algorithmic uses of the Feferman-Vaught theorem. Ann. Pure Appl. Logic, 126(1-3):159-213, 2004. Google Scholar
  24. Anatoly I. Maltsev. Untersuchungen aus dem Gebiete der mathematischen Logik. Matematicheskii Sbornik, n.s.(1):323-336, 1936. Google Scholar
  25. Jaroslav Nešetřil and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. Google Scholar
  26. Eric Rosen. Some aspects of model theory and finite structures. Bull. Symbolic Logic, 8(3):380-403, 2002. Google Scholar
  27. Benjamin Rossman. Homomorphism preservation theorems. J. ACM, 55(3):15:1-15:53, 2008. Google Scholar
  28. Abhisekh Sankaran. A generalization of the Łoś-Tarski preservation theorem. CoRR, abs/1609.06297, 2016. URL: http://arxiv.org/abs/1609.06297.
  29. Abhisekh Sankaran. A finitary analogue of the downward Löwenheim-Skolem property. CoRR, abs/1705.04493, 2017. URL: http://arxiv.org/abs/1705.04493.
  30. Abhisekh Sankaran, Bharat Adsul, and Supratik Chakraborty. A generalization of the Łoś-Tarski preservation theorem over classes of finite structures. In MFCS 2014, Budapest, Hungary, August 25-29, 2014, Part I, pages 474-485, 2014. Google Scholar
  31. Abhisekh Sankaran, Bharat Adsul, and Supratik Chakraborty. A generalization of the Łoś-Tarski preservation theorem. Ann. Pure Appl. Logic, 167(3):189-210, 2016. Google Scholar
  32. J. W. Thatcher and J. 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. Google Scholar
  33. Wolfgang Thomas. Ehrenfeucht games, the composition method, and the monadic theory of ordinal words, pages 118-143. Springer Berlin Heidelberg, 1997. Google Scholar
  34. Jouko Väänänen. Pseudo-finite model theory. Mat. Contemp, 24(8th):169-183, 2003. 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