On the Expressive Power of First-Order Logic with Built-In Predicates
237 pages, year of publication: 2002
price: 40.50 €
This dissertation investigates the expressive power of first-order logic on structures with built-in predicates such as linear ordering, addition, and multiplication.
The main results are subdivided into the following 3 topics:
Arithmetic and counting quantifiers:
We show that Presburger arithmetic is closed under unary counting quantifiers. This, in particular, leads to an easy proof of the known result that reachability and connectivity of finite graphs are not expressible in first-order logic with unary counting quantifiers and built-in addition.
The Crane Beach Conjecture (CBC, for short):
Here we consider string-languages that have a neutral letter
that may be inserted or deleted in any string without changing its
membership or non-membership in the language.
The CBC is closely related to uniformity conditions of the circuit complexity class AC0
on the one hand, and to collapse results in database theory, on the other hand.
We give a state-of-the-art overview of what is known about the CBC,
exposing negative as well as positive instances of the CBC.
Collapse results in database theory:
Most so-called natural generic collapse results (for <-generic queries) known so far restrict attention to finite databases. Via an Ehrenfeucht-Fraissť game approach we obtain collapse results also for infinite (N-embeddable and N-representable) databases.