DFG-Graduiertenkolleg Mathematische Logik und Anwendungen

Graduiertenkolloquium WS 2006/2007

Vorträge

• 27.11.2006
  Herr Prof. Yuri Ershov
  Computable numberings Abstract
  

• 04.12.2006
  Herr Dr. Dino DiStefano
  On-the-fly shape analysis Abstract
  

• 22.01.2007
  Herr Prof. Victor Dalmau
  Constraint Satisfaction, Logic, and Dualities Abstract
  

• 29.01.2007
  Frau Nina Frohn
  Axiomatisierung der Elementary Type Conjecture Abstract
  

• 05.02.2007
  Herr Bijan Afshordel
  Pseudoendliche Körper und generische Automorphismen Abstract
  

• 12.02.2007
  Frau Prof. Katrin Tent
  Stabile pseudo-endliche Gruppen Abstract
  

Tagungen/Workshops

• 27. - 28. Oktober
  Model Checking and Semantic Web Rule Languages
  

• 25. - 27. November
  Conference on the Model Theory of Fields
  

Abstracts

• On-the-fly shape analysis
  
  
  In this talk I will present a novel technique for shape analysis tailored to the verification of complex data structures found in real industrial software.
  



• Constraint Satisfaction, Logic, and Dualities
  
  
  For every relational structure B, the (non-uniform) constraint satisfaction problem associated to B, CSP(B), is the following computational problem: given a relational structure A, is there a homomorphism from A to B?. The complexity of the problem CSP(B) varies depending on the election of the structure B. In the last few years much effort has been invested in the project of classifying the computational complexity of CSP(B), for every B. An useful tool in this study has been the consideration of the logics that can express CSP(B). Perhaps the best illustration of this approach is the fact that a good number of the tractable cases of the problem identified so far can be explained, in an uniform way, as those CSP(B) definable in Datalog. In this talk we shall consider three logics that have been considered in the study of constraint satisfaction: datalog, linear datalog, and first-order logic. In the realm of CSP, each one of these logics has a counterpart in the form of dualities. In this talk we shall survey this connection. We shall discuss also the problem of deciding whether a given CSP(B) is definable in each one of these logics.
  



• Axiomatisierung der Elementary Type Conjecture
  
  
  Zu einem Körper K betrachten wir eine bestimmte Automorphismengruppe G(K,p). Die Elementary Type Conjecture benennt notwendige und hinreichende Bedingungen dafür, dass eine (beliebige pro-p-) Gruppe G endlichen Rangs isomorph zu einer solchen Automorphismengruppe G(K,p) ist.
  
  In dem Vortrag werde ich zunächst die Aussage der Elementary Type Conjecture erklären. Im Anschluss daran werde ich zeigen, dass die durch die Elementary Type Conjecture beschriebene Klasse von Gruppen in einer geeigneten erststufigen Sprache axiomatisierbar ist.
  
  
  
• Pseudoendliche Körper und generische Automorphismen
  
  
  Pseudoendliche Körper sowie Körper mit generischem Automorphismus bilden wichtige Beispiele sogenannter supereinfacher Strukturen. Es ist bekannt, dass jeder pseudoendliche Körper elementar äquivalent zum Fixkörper eines Körpers mit generischem Automorphismus ist. Ich werde in meinem Vortrag zeigen, dass jeder pseudoendliche Körper sogar isomorph zum Fixkörper eines generischen Automorphismus ist.
  
  
  
• Stabile pseudo-endliche Gruppen
  
  
  Ich werde erklären, warum stabile pseudo-endliche Gruppen einen auflösbaren Normalteiler von endlichem Index haben.