Paper: y=2x vs. y=3x (at LICS 1993)
Authors: Damien Niwinski Alexei StolboushkinAbstract
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} }