Seventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1992)

Paper: Generalized quantifiers and pebble games on finite structures (at LICS 1992)

Authors: Kolaitis, P.G. Vaananen, J.A.


Generalized quantifiers in the realm of finite structures are studied and combined with an infinitary logic L∞ωω to obtain new logics that can be used to express polynomial-time properties that are not definable in the original logic. It is shown that equivalence of finite structures relative to the new logics can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht-Fraisse games. This time-theoretic characterization is combined with sophisticated combinatorial tools in order to investigate the scopes and limits of generalized quantifiers in finite model theory


    author = 	 {Kolaitis, P.G. and Vaananen, J.A.},
    title = 	 {Generalized quantifiers and pebble games on finite structures},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1992},
    year =	 1992,
    editor =	 {Andre Scedrov},
    month =	 {June}, 
    pages =      {348--359},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}