Arbeitsgruppe Berechenbarkeitstheorie über algebraischen Strukturen

Kontakt

PD Dr. Christine Gaßner

Institut für Mathematik und Informatik

Walther-Rathenau-Straße 47

17489 Greifswald

Telefon +49 3834 420 4610

Telefax + 49 3834 86-4640

gassnerc(at)uni-greifswald(dot)de

Die Berechenbarkeitstheorie über algebraischen Strukturen ist im Wesentlichen ein Teilgebiet der mathematischen Logik mit Bezügen zur Theoretischen Informatik. Sie beschäftigt sich mit verschiedenen Berechnungsmodellen, in denen u.a. auch die Operationen algebraischer Strukturen als Basisoperationen zugelassen werden, und umfasst Verallgemeinerungen der klassischen Berechenbarkeitstheorie.


Aktuelles

 

Kolloquium (07.11.2016, 16.00 Uhr)

Rupert Hölzl (München): Absolutely undecidable sets (Folien)

weitere Informationen

 

Colloquium Logicum 2016 (September 2016)

Christine Gaßner: BSS RAM's with ν-Oracle and the Axiom of Choice

 

Kolloquium auf Hiddensee (09.08.2016, 13 Uhr)

André Nies (Auckland): Zufälligkeit und Quantenberechnung

 

Arbeitstreffen (08. August 2016 bis zum 12. August 2016)

Das Arbeitstreffen zum Thema „Berechenbarkeit und das BSS-Modell" fand in Kloster auf Hiddensee statt.


Forschung

Forschungsschwerpunkte

  • Berechenbarkeit über algebraischen Strukturen
  • Klassifizierung von algebraischen Problemen nach Unentscheidbarkeitsgrad
  • Komplexitätsschranken und P-NP-Probleme
  • Das BSS-RAM-Modell und Moschovakis-Operatoren (Definitionen)

Siehe dazu auch:

  • T. Zerjatke: Möglichkeiten und Grenzen des DNA-Computings im Hinblick auf PSPACE (Diplomarbeit)

Themen für Bachelor-, Master- und Doktorarbeiten

Falls Sie Interesse an einem Thema zu folgenden Schwerpunkten haben, dann wenden Sie sich bitte an: gassnerc(at)uni-greifswald(dot)de.

Themenschwerpunkte:

  • Die Leistungsstärke von Berechnungsmodellen zwischen endlichen Automaten und BSS-RAMs über algebraischen Strukturen. Angeregt wurde dieser Themenschwerpunkt auf dem Arbeitstreffen 2014 (Schwerpunkte). Es geht dabei sowohl um das Sammeln von Anwendungsbeispielen und den Vergleich zwischen verschiedenen Automatentypen als auch um Beweise zur Leistungsstärke einzelner Automatentypen und Beweise zur Unlösbarkeit von Problemen durch gewisse Automaten.
  • Einordnung der vorhandenen Berechnungsmodelle
  • Die Bedeutung des Auswahlaxioms
    • in der Berechenbarkeitstheorie
    • in der Graphentheorie
    usw.