Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-173 | 22nd December 2011 18:02

Regular Languages in MAJ[<] with three variables

RSS-Feed




TR11-173
Authors: Christoph Behle, Andreas Krebs
Publication: 23rd December 2011 11:51
Downloads: 3326
Keywords: 


Abstract:

We consider first order logic over words and show FO+MOD[<] is contained in MAJ[<] with three variables.
It is known that for the classes FO[<], FO+MOD[<], FO+GROUP[<] three variables suffice. In the case of MOD[<] even two variables are sufficient.

As a consequence we know that if TC^ 0 neq NC^1 then for every regular language describable in MAJ[<] three variables are sufficient.



ISSN 1433-8092 | Imprint