Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
5 results

Definability of linear equation systems over groups and rings

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.&nbsp;[&hellip;]
Published on November 14, 2013
Volume 9, Issue 4

Complexity of Problems of Commutative Grammars

Eryk Kopczynski.
We consider commutative regular and context-free grammars, or, in other words, Parikh images of regular and context-free languages. By using linear algebra and a branching analog of the classic Euler theorem, we show that, under an assumption that the terminal alphabet is fixed, the membership&nbsp;[&hellip;]
Published on March 25, 2015
Volume 11, Issue 1

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;]
Published on April 25, 2018
Volume 14, Issue 2

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;]
Published on November 6, 2017
Volume 13, Issue 4

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;]
Published on July 25, 2019
Volume 15, Issue 3
  • < Previous
  • 1
  • Next >