10 citations · 12 across the 14 of their papers we have counts for
4 papers · 2 filters
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…
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…
Game Comonads & Generalised Quantifiers
Adam Ó Conghaile, Anuj Dawar
Game comonads, introduced by Abramsky, Dawar and Wang and developed by Abramsky and Shah, give an interesting categorical semantics to some Spoiler-Duplicator games that are common…
Relativization of Gurevich's Conjectures
Anatole Dahan, Anuj Dawar
Gurevich (1988) conjectured that there is no logic for or for . For the latter complexity class, he also showed that the existence of a…