Eleventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1996)

Paper: Counting Modulo Quantifiers on Finite Linearly Ordered Trees (at LICS 1996)

Authors: Juha Nurmonen


We give a combinatorial method for proving elementary equivalence in first-order logic FO with counting modulo n quantifiers D_n. Inexpressibility results for FO(D_n) with built-in linear order are also considered. We show that certain divisibility properties of word models are not definable in FO(D_n). We also show that the height of complete n-ary trees cannot be expressed in FO(D_n) with linear order. Interpreting the predicate y=nx as a complete n-ary tree, we show that the predicate y=(n+1)x cannot be defined in FO(D_n) with linear order. This proves the conjecture of Niwinski and Stolboushkin. We also discuss connection between our results and the well-known open problem in circuit complexity theory, whether ACC=NC^1.


    author = 	 {Juha Nurmonen},
    title = 	 {Counting Modulo Quantifiers on Finite Linearly Ordered Trees},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1996},
    year =	 1996,
    editor =	 {Edmund M. Clarke},
    month =	 {July}, 
    pages =      {484-493},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}