Logic in Computer Science (LICS 1993)

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

Authors: Damien Niwinski Alexei 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 = 	 {Damien Niwinski and Alexei Stolboushkin},
    title = 	 {y=2x vs. y=3x},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1993},
    year =	 1993,
    editor =	 {Moshe Vardi},
    month =	 {June}, 
    pages =      {172--178},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }