3 citations · 8 across the 12 of their papers we have counts for
15 papers
Pseudo-finiteness of arbitrary graphs of bounded shrub-depth
Abhisekh Sankaran
We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the classes of arbitrary graphs that have tree models of height…
Feferman-Vaught Decompositions for Prefix Classes of First Order Logic
Abhisekh Sankaran
The Feferman-Vaught theorem provides a way of evaluating a first order sentence on a disjoint union of structures by producing a decomposition of into sentences which can b…
MSO Undecidability for Hereditary Classes of Unbounded Clique-Width
Anuj Dawar, Abhisekh Sankaran
Seese's conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it w…
Some classical model theoretic aspects of bounded shrub-depth classes
Abhisekh Sankaran
We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the class of -labeled arbitrary graphs whose underlying…
Extension Preservation in the Finite and Prefix Classes of First Order Logic
Anuj Dawar, Abhisekh Sankaran
It is well known that the classic Łoś-Tarski preservation theorem fails in the finite: there are first-order definable classes of finite structures closed under extensions which ar…
Clique-Width of Point Configurations
Onur Çağırıcı, Petr Hliněný, Filip Pokrývka +1
While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose…
Exact Crossing Number Parameterized by Vertex Cover
Petr Hliněný, Abhisekh Sankaran
We prove that the exact crossing number of a graph can be efficiently computed for simple graphs having bounded vertex cover. In more precise words, Crossing Number is in FPT when…
Revisiting the generalized Łoś-Tarski theorem
Abhisekh Sankaran
We present a new proof of the generalized Łoś-Tarski theorem () introduced in [1], over arbitrary structures. Instead of using -saturation as in [1], we constru…
A Generalization of the Łoś-Tarski Preservation Theorem - Dissertation Summary
Abhisekh Sankaran
This article gives a summary of the author's Ph.D. dissertation (arXiv:1609.06297). In addition to an overview of notions and results, it also provides sketches of various proofs a…
A Finitary Analogue of the Downward Löwenheim-Skolem Property
Abhisekh Sankaran
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 t…
A Generalization of the Łoś-Tarski Preservation Theorem
Abhisekh Sankaran
In this dissertation, we present for each natural number , semantic characterizations of the and prefix classes of first order logic…
A Generalization of the Łoś-Tarski Preservation Theorem over Classes of Finite Structures
Abhisekh Sankaran, Bharat Adsul, Supratik Chakraborty
We investigate a generalization of the Łoś-Tarski preservation theorem via the semantic notion of \emph{preservation under substructures modulo -sized cores}. It was shown earli…
Generalizations of the Los-Tarski Preservation Theorem
Abhisekh Sankaran, Bharat Adsul, Supratik Chakraborty
We present new preservation theorems that semantically characterize the and prefix classes of first order logic, for each natural number…
Preservation under Substructures modulo Bounded Cores
Abhisekh Sankaran, Bharat Adsul, Vivek Madan +2
We investigate a model-theoretic property that generalizes the classical notion of "preservation under substructures". We call this property \emph{preservation under substructures…
On Semantic Generalizations of the Bernays-Schönfinkel-Ramsey Class with Finite or Co-finite Spectra
Abhisekh Sankaran, Supratik Chakraborty
Motivated by model-theoretic properties of the BSR class, we present a family of semantic classes of FO formulae with finite or co-finite spectra over a relational vocabulary Σ. A…