Logic in Computer Science (LICS 1994)

Paper: Generalized quantifiers for simple properties (at LICS 1994)

Authors: Martin Otto

Abstract

We consider extensions of fixed-point logic by means of generalized quantifiers in the context of descriptive complexity. By the well-known theorem of N. Immerman and M. Vardi, fixed-point logic captures PTime over linearly ordered structures. It fails, however, to express even most fundamental structural properties, like simple cardinality properties, in the absence of order. We concentrate on extensions by generalized quantifiers which serve to adjoin simple or basic structural properties. An abstract notion of simplicity is put forward which isolates those structural properties, that can be characterized in terms of a concise structural invariant. The key examples are provided by all monadic and cardinality properties in a very general sense. The main theorem establishes that no extension by any family of such simple quantifiers can cover all of PTime. These limitations are proved on the basis of the semantically motivated notion of simplicity; in particular there is no implicit bound on the arities of the generalized quantifiers involved. Quite to the contrary, the natural applications concern infinite families of quantifiers adjoining certain structural properties across all arities in a uniform way

BibTeX

  @InProceedings{Otto-Generalizedquantifi,
    author = 	 {Martin Otto},
    title = 	 {Generalized quantifiers for simple properties},
    booktitle =  {Proceedings of the Ninth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1994},
    year =	 1994,
    editor =	 {Samson Abramsky},
    month =	 {July}, 
    pages =      {30--39},
    location =   {Paris, France}, 
    publisher =	 {IEEE Computer Society Press}
  }