Counting module quantifiers on finite structures

We give a combinatorial method for proving elementary equivalence in first- order logic FO with counting module n quantifiers D-n, inexpressibility res ults for FO(D-n) with built-in linear order are also considered. For instan ce, the class of linear orders of length divisible by n+1 cannot be express ed in FO(D-n). Using this result we prove that comparing cardinalities or c onnectivity of ordered graphs are not definable in FO(D-n). We also show th at the height of complete n-ary trees cannot be expressed in FO(D-n) with l inear order. Interpreting the predicate y = nx as a complete n-ary tree, we show that the predicate y = pr cannot be defined in FO(D-n) with linear or der, whenever p has a prime factor that does not divide n. This solves the problem raised by Niwinski and Slolboushkin (LICS '93), We also discuss a c onnection between our results and the well-known open problem in circuit co mplexity theory, whether ACC = NC1. (C) 2000 Academic Press.