Login
Talks & Seminars
Title: A finitary analogue of the downward Lowenheim-Skolem property
Dr. Abhisekh Sankaran, Institute of Mathematical Sciences (IMSc) Chennai.
Date & Time: September 20, 2017 11:00
Venue: Room 105, 1st Floor, New CSE Building
Abstract:
We present a model-theoretic property of finite structures, that can be seen as a finitary analogue of the well-studied downward Lowenheim-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. Furthermore, by considering relations other than "substructure" in the EBSP definition, many more computationally interesting classes turn out to satisfy (the corresponding variant of) EBSP: these include graph classes of bounded tree-width, those of bounded clique-width, and those of bounded rank-width. 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 (algorithmic meta-theorems). 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.
Speaker Profile:
Abhisekh Sankaran is currently a post-doctoral fellow at the Institute of Mathematical Sciences (IMSc) Chennai. Prior to joining IMSc, he completed his Ph.D. at the Department of Computer Science and Engineering at IIT Bombay in August 2016. Abhisekh's research interests are in model theory, both classical and finite, and more generally, in the subjects of mathematical logic and logic in computer science.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback