#### Alladi Ramakrishnan Hall

#### A finitary analogue of the downward Lowenheim-Skolem property

#### Abhisekh Sankaran

##### IMSc

*We present a model-theoretic property of finite structures, that can be*

seen to be a finitary analogue of the well-studied downward

L\"owenheim-Skolem property from classical model theory. We call this

property the *equivalent bounded substructure property*, denoted EBSP.

Intuitively, EBSP states that a large finite structure contains a small

``logically similar'' substructure, where logical similarity means

indistinguishability with respect to sentences of FO/MSO 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, ranked or

partially ranked) and nested words, and various classes of graphs, such as

cographs, graph classes of bounded tree-depth, those of bounded shrub-depth

and m-partite cographs. Further, EBSP remains preserved in the classes

generated from the above using various well-studied operations, such as

complementation, transpose, the line-graph operation, disjoint union, join,

and various products including the Cartesian and tensor products.

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 FO/MSO definable properties of the large structure. We

conclude by presenting a strengthening of 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.

Done