Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

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 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 

André Hernich