Seminar Logik, Komplexität, Spiele: Automatische Strukturen

WS 2011/12

Aktuelles

  • Die Vorträge am Freitag finden - entgegen der Ankündigung - ebenfalls in unserem Seminarraum statt.
  • Bitte beachten Sie die Übersicht zum zeitlichen Ablauf des Seminars.

Organisation

Die Vorträge finden statt am:

  • Dienstag, 31. Januar, in unserem Seminarraum (Raum 4116, E1, Ahornstr. 55)
  • Freitag, 03. Februar, in unserem Seminarraum (Raum 4116, E1, Ahornstr. 55)
Die Vorträge können wahlweise auf deutsch oder englisch gehalten werden.

Zeitplan

24.10.Gliederung, Konzeption
14.11.Ausarbeitung
12.12.Endgültige Fassung
09.01.Folien
31.01., 03.02.Vorträge

Programm

Dienstag, 31. Januar
9:009:40Eugen StollInterpretationen und vollständige Strukturen
9:5010:30Stefan JaaxModel-Checking Spiele auf automatischen Strukturen
11:0011:40Harald RöhlingInvarianten automatischer Präsentationen und semi-synchrone Transduktionen
13:0013:40Roman MatzuttIst Cantors Theorem automatisch?
13:5014:30Jonathan Schmidt-DominéVon automatischen Strukturen zu Borel-Strukturen
15:0015:40Felix LantinAutomatische Gruppen: Abelsche und Euklidische Gruppen
15:5016:30Robert Ivo MeiAutomatische Gruppen: Nilpotente Gruppen sind nicht automatisch
Freitag, 03. Februar
9:009:40Bettina HardyMengen-Interpretationen
9:5010:30Marlin FrickenschmidtWachstumsfunktionen und nicht-automatische Strukturen
11:0011:40Sebastian JungesZufalls-Strukturen und eine Charakterisierung automatischer Boolescher Algebren
11:5012:30Lota LimarevaDie additive Gruppe der rationalen Zahlen
14:0014:40Christian FrischKomplexitätsprobleme für automatische Strukturen
14:5015:30Svenja SchalthöferDas Isomorphie-Problem für Klassen von automatischen Strukturen

Inhalt

Automatic structures are first-order structures, whose elements are identified with the words of a regular language, and whose functions and relations are representable by synchronous finite automata. Finite structures, for instance, are trivially automatic, but the really interesting examples of automatic structures are infinite ones, such as Presburger arithmetic and the infinite binary tree with prefix order and equal length predicate.

Automatic structures are interesting because they provide a natural family of infinite structures that are finitely presentable (by the automata that describe their functions and relations) in such a way that important computational problems, such as first-order model checking or query evaluation, can be handled effectively. Automatic structures thus provide a domain of structures that is relevant for the programme of computational model theory, i.e. the study of logical definability and computational complexity of finitely presentable structures. Computational model theory builds on, and extends finite model theory; it translates computational problems to logical ones and tackles them using tools of logic. This approach has been quite successful for finite structures where we have numerous characterisation theorems relating machine models and computational complexity classes with various logics and definability within these logics. The traditional limitation to finite structures is, however, unnecessarily restrictive, as there are many applications, e.g., in the fields of databases or automated verification, which naturally call for infinite models. This motivates the extension of methods of finite model theory to relevant domains of infinite structures. Of course, infinite objects handled by computers must be finitely representable in some way, and given a finite representation of a structure, the relevant computational problems concerning the structure should be effectively solvable. Automatic structures provide one such framework based on a robust and sufficiently simple, and very well-studied model of computation.

Automatic structures are also relevant in certain branches of mathematics, such as computational group theory. Indeed, the best studied examples of automatic structures are automatic groups, i.e. finitely generated groups with an automatic Cayley graph. The importance of this notion in computational group theory comes from the fact that an automatic presentation of a group yields (efficient) algorithmic solutions for computational problems (e.g. the word problem) that are undecidable in the general case. There are further interesting connections to the theories of automatic sequences and decidable subsystems of arithmetic. The notion of an automatic structure can be modified and generalised in many directions. By using automata over infinite words, we obtain the notion of omega-automatic structures which, contrary to automatic structures, may have uncountable cardinality. Examples of omega-automatic structures include the additive group of the real numbers, and the tree of finite and infinite binary sequences. Similarly one can use tree-automata to define term-automatic structures.

Einführungsliteratur

Folgende Übersichtsartikel sind für alle Themen als Einführungsliteratur empfohlen: [KhMi07, BGR10]

Themen

ThemaVortragende(r)Betreuer(in)Literatur
Interpretationen und vollständige StrukturenEugen StollRoman Rabinovich[BlGr04, Bl99]
Mengen-InterpretationenBettina HardyRoman Rabinovich[CoLo07]
Wachstumsfunktionen und nicht-automatische StrukturenMarlin FrickenschmidtBernd Puchala[BlGr04, Bl99]
Zufalls-Strukturen und eine Charakterisierung automatischer Boolescher AlgebrenSebastian JungesWied Pakusa[KuNiRuSt07]
Die additive Gruppe der rationalen ZahlenLota LimarevaFaried Abu Zaid[Ts11]
Automatische Gruppen: Abelsche und Euklidische GruppenFelix LantinWied Pakusa[Ep92, Fa92]
Automatische Gruppen: Nilpotente Gruppen sind nicht automatischRobert Ivo MeiWied Pakusa[Ep92, Fa92]
Invarianten automatischer Präsentationen und semi-synchrone TransduktionenHarald RöhlingBernd Puchala[Bar06, Bar07]
Von automatischen Strukturen zu Borel-StrukturenJonathan Schmidt-DominéFaried Abu Zaid[HjKhMoNi08]
Ist Cantors Theorem automatisch?Roman MatzuttBernd Puchala[Ku03]
Komplexitätsprobleme für automatische StrukturenChristian FrischFrancicleber Ferreira[KuLo09]
Das Isomorphie-Problem für Klassen von automatischen StrukturenSvenja SchalthöferRoman Rabinovich[KuLiLo10]
Model-Checking Spiele auf automatischen StrukturenStefan JaaxFaried Abu Zaid[Kai08]

Literatur

Zuordnung

  • Informatik (B.Sc.)/Seminar Informatik
  • Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
  • Informatik (M.Sc.)/Seminar Theoretische Informatik
  • Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)
  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/Modul Algebra
  • Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Voraussetzungen

  • Modul Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Bernd Puchala, Roman Rabinovich, Faried Abu Zaid, Wied Pakusa