$Y = 2x$ vs. $y = 3x$

&
Journal of Symbolic Logic 62 (2):661-672 (1997)
  Copy   BIBTEX

Abstract

We show that no formula of first order logic using linear ordering and the logical relation $y = 2x$ can define the property that the size of a finite model is divisible by 3. This answers a long-standing question which may be of relevance to certain open problems in circuit complexity

Categories

Keywords

Reprint years

Other Versions

original Stolboushkin, Alexei; Niwiński, Damian (1997) "Y = 2x vs. Y = 3x". Journal of Symbolic Logic 62(2):661-672

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,423

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Y = 2x vs. Y = 3x.Alexei Stolboushkin & Damian Niwiński - 1997 - Journal of Symbolic Logic 62 (2):661-672.
On the complexity of the successivity relation in computable linear orderings.Rod Downey, Steffen Lempp & Guohua Wu - 2010 - Journal of Mathematical Logic 10 (1):83-99.
The finite model property for knotted extensions of propositional linear logic.C. J. van Alten - 2005 - Journal of Symbolic Logic 70 (1):84-98.
The finite model property for various fragments of intuitionistic linear logic.Mitsuhiro Okada & Kazushige Terui - 1999 - Journal of Symbolic Logic 64 (2):790-802.
The complexity of definability by open first-order formulas.Carlos Areces, Miguel Campercholi, Daniel Penazzi & Pablo Ventura - 2020 - Logic Journal of the IGPL 28 (6):1093-1105.
Partial-order Boolean games: informational independence in a logic-based model of strategic interaction.Julian Bradfield, Julian Gutierrez & Michael Wooldridge - 2016 - Synthese 193 (3):781-811.
Inferring a linear ordering over a power set.Ran Spiegler - 2001 - Theory and Decision 51 (1):31-49.
On the Decision Problem for Two-Variable First-Order Logic.Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
On the decision problem for two-variable first-order logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.

Analytics

Added to PP
2013-11-02

Downloads
22 (#981,487)

6 months
6 (#888,477)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references