1 citations · 1 across the 3 of their papers we have counts for
4 papers · 1 filter
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…