Search

• < Previous
• 1
• Next >

---

A note on first-order spectra with binary relations

Eryk Kopczynski ; Tony Tan.

The spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at least three variables. We show that for every such sentence $\Phi$, there is a sentence $\Phi'$ that uses the same number&nbsp;[&hellip;]

---

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;]

---