Regular Languages in MAJ[>] with three variables.
Christoph Behle, Andreas Krebs · Electronic colloquium on computational complexity · 2011
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 , NC then for every regular language describable in MAJ[<] three variables are sufficient.