3 results
Anuj Dawar ; Eryk Kopczynski ; Bjarki Holm ; Erich Grädel ; Wied Pakusa.
Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability. […]
Published on November 14, 2013
Anuj Dawar ; Eryk Kopczyński.
We establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes. In particular, we show that MSO obeys a zero-one law on the class of connected planar graphs, the class of connected graphs of […]
Published on July 25, 2019
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 in finite model theory. In particular they expose connections between one-sided and two-sided games, and parameters […]
Published on July 23, 2024