# Mitarbeiterseminar Logik in der Informatik

Freitag, 21. April 2006, 11:15 Uhr

RUD 25, Raum 4.410
## Comparing the succinctness of various logics

Nicole Schweikardt

Humboldt-Universität zu Berlin

Succinctness is a natural measure for comparing the strength of
different logics. Intuitively, a logic *L*_{1} is more succinct than
another logic *L*_{2} if all properties that can be expressed in *L*_{2} can
be expressed in *L*_{1} by formulas of (approximately) the same size, but
some properties can be expressed in *L*_{1} by (significantly) smaller
formulas. In this talk I will present a number of succinctness
results concerning first-order logic, monadic second-order logic, and
fragments of these logics. In particular, I want to give an overview
of proof techniques for showing lower bounds on succinctness,
including the automata-theoretic approach, a method using succinct
encodings of large numbers, and the Adler-Immerman game.