Paper: y=2x vs. y=3x (at LICS 1993)

Authors: Damian Niwinski Alexei P. Stolboushkin

Abstract

It is shown 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 that may be of relevance to certain open problems in circuit complexity

BibTeX

  @InProceedings{NiwinskiStolboushki-y2xvsy3x,
    author = 	 {Damian Niwinski and Alexei P. Stolboushkin},
    title = 	 {y=2x vs. y=3x},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS 1993)},
    year =	 {1993},
    month =	 {June}, 
    pages =      {172--178},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }