Buch, Deutsch, 237 Seiten, Format (B × H): 145 mm x 210 mm
Buch, Deutsch, 237 Seiten, Format (B × H): 145 mm x 210 mm
ISBN: 978-3-8325-0017-7
Verlag: Logos
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.
