## Paper: Logical hierarchies in PTIME (at LICS 1992)

**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} }