8 papers · 1 filter
Preservation Theorems in Semiring Semantics
Sophie Brinke, Anuj Dawar, Erich Grädel +1
We study the status of preservation theorems such as the ÅoÅ-Tarski theorem and the homomorphism preservation theorem in the context of semiring semantics. Semiring semantics has…
Undefinability of Approximation of 2-to-2 Games
Anuj Dawar, Bálint Molnár
Recent work by Atserias and Dawar (J. Log. Comp 2019) and Tucker-Foltz (LMCS 2024) has established undefinability results in fixed-point logic with counting (FPC) corresponding to…
Towards the type safety of Pure Subtype Systems (Full version)
Valentin Pasquale, Ãlvaro GarcÃa-Pérez
Hutchins' Pure Subtype Systems (PSS) offer a unified framework for types and terms, promising significant advancements in language design for features like dependent types and high…
Arity hierarchies for quantifiers closed under partial polymorphisms
Anuj Dawar, Lauri Hella, Benedikt Pago
We investigate the expressive power of generalized quantifiers closed under partial polymorphism conditions motivated by the study of constraint satisfaction problems. We answer a…
Characterizing NC1 with Typed Monoids
Anuj Dawar, Aidan T. Evans
Krebs et al. (2007) gave a characterization of the complexity class TC0 as the class of languages recognized by a certain class of typed monoids. The notion of typed monoid was int…
Symmetric Proofs in the Ideal Proof System
Anuj Dawar, Erich Grädel, Leon Kullmann +1
We consider the Ideal Proof System (IPS) introduced by Grochow and Pitassi and pose the question of which tautologies admit symmetric proofs, and of what complexity. The symmetry r…