Sankaran, Abhisekh
A Finitary Analogue of the Downward LöwenheimSkolem Property
Abstract
We present a modeltheoretic property of finite structures, that can be seen to be a finitary analogue of the wellstudied downward LöwenheimSkolem property from classical model theory. We call this property the *Lequivalent bounded substructure property*, denoted LEBSP, where L is either FO or MSO. Intuitively, LEBSP 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 treedepth, those of bounded shrubdepth and npartite cographs. Further, LEBSP remains preserved in the classes generated from the above by operations that are implementable using quantifierfree 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 Ldefinable properties of the large structure. We conclude by presenting a strengthening of LEBSP, that asserts "logical selfsimilarity 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.
BibTeX  Entry
@InProceedings{sankaran:LIPIcs:2017:7707,
author = {Abhisekh Sankaran},
title = {{A Finitary Analogue of the Downward L{\"o}wenheimSkolem Property}},
booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
pages = {37:137:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770453},
ISSN = {18688969},
year = {2017},
volume = {82},
editor = {Valentin Goranko and Mads Dam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7707},
URN = {urn:nbn:de:0030drops77074},
doi = {10.4230/LIPIcs.CSL.2017.37},
annote = {Keywords: downward LowenheimSkolem theorem, trees, nested words, treedepth, cographs, tree representation, translation schemes, composition lemma, f.p.t., log}
}
16.08.2017
Keywords: 

downward LowenheimSkolem theorem, trees, nested words, treedepth, cographs, tree representation, translation schemes, composition lemma, f.p.t., log 
Seminar: 

26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Issue date: 

2017 
Date of publication: 

16.08.2017 