Lics

ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Seventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1992)

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

Authors: Phokion G. Kolaitis Jouko A. Väänänen

Abstract

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

BibTeX

  @InProceedings{Vnnen-Generalizedquantifi,
    author = 	 {Phokion G. Kolaitis and Jouko A. Väänänen},
    title = 	 {Generalized quantifiers and pebble games on finite structures},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 1992)},
    year =	 {1992},
    month =	 {June}, 
    pages =      {348--359},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2022-10-3113:49
Sam Staton