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