Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Comparing the succinctness of various logics

Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L₁ is more succinct than another logic L₂ if all properties that can be expressed in L₂ can be expressed in L₁ by formulas of (approximately) the same size, but some properties can be expressed in L₁ 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.