Paper: Logical hierarchies in PTIME (at LICS 1992)

Authors: Lauri Hella

Abstract

A generalized quantifier is n-ary if it binds any finite number of formulas, but at most n variables in each formula. It is proved that for each integer n, there is a property of finite models which is expressible in fixpoint logic, or even in DATALOG, but not in the extension of first-order logic by any set of n-ary quantifiers. It follows that no extension of first-order logic by a finite set of quantifiers captures all DATALOG-definable properties. Furthermore, it is proved that for each integer n, there is a LOGSPACE-computable property of finite models which is not definable in any extension of fixpoint logic by n-ary quantifiers. Hence, the expressive power of LOGSPACE, and a fortiori, that of PTIME, cannot be captured by adding to fixpoint logic any set of quantifiers of bounded arity

BibTeX

  @InProceedings{Hella-Logicalhierarchiesi,
    author = 	 {Lauri Hella},
    title = 	 {Logical hierarchies in PTIME},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 1992)},
    year =	 {1992},
    month =	 {June}, 
    pages =      {360--368},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }