Connections between partially ordered connectives and Henkin quantifiers are considered. It is proved that the logic with all partially ordered connectives and the logic with all Henkin quantifiers coincide. This implies that the hierarchy of partially ordered connectives is strongly hierarchical and gives several nondefinability results between some of them. It is also deduced that each Henkin quantifier can be defined by a quantifier of the form equation imagewhat is a strengthening of the Walkoe result. MSC: 03C80.

This book is a relatively self-contained introduction to the subject, which includes the necessary background material, as well as numerous examples and exercises.

The book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logics that are important in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages; their model theory is studied in full detail. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way (...) that the respective parts on model theory and descriptive complexity theory may be read independently. This second edition is a thoroughly revised and enlarged version of the original text. (shrink)

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not always (...) true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]. (shrink)

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a familyQof generalized quantifiers expressing a complexity classC, what is the expressive power of first order logic FO(Q) extended by the quantifiers inQ? From previously studied examples, one would expect that FO(Q) capturesLC, i.e., logarithmic space relativized to an oracle inC. We show that this is not always true. However, after studying the problem from a (...) general point of view, we derive sufficient conditions onCsuch that FO(Q) capturesLC. These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, byNP. As an application of this result, it follows that first order logic extended by Henkin quantifiers capturesLNP. This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many familiesQof generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform, vol. 18, 1993]. (shrink)