Published on Sun Apr 30 2017
Modulo quantifiers over functional vocabularies extending addition
See More ...
We show that first order logic (FO) and first order logic extended with
modulo counting quantifiers (FOMOD) over purely functional vocabularies which
extend addition, satisfy the Crane beach property (CBP) if the logic satisfies
a normal form (called positional normal form). This not only shows why logics
over the addition vocabulary have the CBP but also gives new CBP results, for
example for the vocabulary which extends addition with the exponentiation
function. The above results can also be viewed from the perspective of circuit
complexity. Showing the existence of regular languages not definable in
FOMOD[<, +, *] is equivalent to the separation of the circuit complexity
classes ACC0 and NC1 . Our theorem shows that a weaker logic , namely,
FOMOD[<,+,2^x] cannot define all regular languages.