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

 Arbeitstreffen 2017

 Vom 06. August 2017 bis zum 11. August 2017 fand ein Arbeitstreffen zum Thema „Berechenbarkeit und Reduzierbarkeit" in Kloster auf Hiddensee statt.

Siehe auch: Preprint 2 2017.

 

Neues Preprint

C. Gaßner: Deterministic Operators for BSS RAM's I (extended abstract).

Preprint-Reihe Ag Berechenbarkeitstheorie über algebraischen Strukturen Greifswald,

Preprint 1 2017  (1. Version 3. April 2017).

 

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.

 

C. Gaßner: Computation over Algebraic Structures and a Classification of Undecidable Problems.
Mathematical Structures in Computer Science,
Verfügbar unter CJO 2016 doi:10.1017/S0960129516000116 (Online: MSCS)

 

 


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.