8 citations · 28 across the 15 of their papers we have counts for
7 papers · 1 filter
Axiomatizing rectangular grids with no extra non-unary relations
Eryk Kopczynski
We construct a formula which axiomatizes non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove th…
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, w…
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 l…
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 complexit…
On the variable hierarchy of first-order spectra
Eryk Kopczynski, Tony Tan
The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we study the hierarchy of first-order spectra…
Regular graphs and the spectra of two-variable logic with counting
Eryk Kopczynski, Tony Tan
The {\em spectrum} of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we show that when restricted to using on…
Definability of linear equation systems over groups and rings
Anuj Dawar, Eryk Kopczynski, Bjarki Holm +2
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 s…