One Quantifier Alternation in First-Order Logic with Modular Predicates

Manfred Kufleitner, Tobias Walter

Adding modular predicates yields a generalization of first-order logic FO over words. The expressive power of FO[<,MOD] with order comparison $x<y$ and predicates for $x \equiv i \…