Search

• < Previous
• 1
• Next >

---

Logical properties of random graphs from small addable classes

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&nbsp;[&hellip;]

---

Bounded degree and planar spectra

Anuj Dawar ; Eryk Kopczyński.

The finite spectrum of a first-order sentence is the set of positive integers that are the sizes of its models. The class of finite spectra is known to be the same as the complexity class NE. We consider the spectra obtained by limiting models to be either planar (in the graph-theoretic sense) or by&nbsp;[&hellip;]

---

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 in finite model theory. In particular they expose connections between one-sided and two-sided games, and parameters&nbsp;[&hellip;]

---