Arbeitsgruppe Logik und Theoretische Informatik

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

gassnercuni-greifswaldde

Leiterin

PD Dr. Christine Gaßner

Mitarbeiter (bis 2017): P. F. Valencia Vizcaíno

Publikationen

Forschungsinformationssystem (Suche unter "Christine Gaßner")

Themen für Bachelor-, Master- und Doktorarbeiten  siehe unten

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

In Vorbereitung:

Mathematisches Kolloquium (Kolloquium des Instituts für Mathematik und Informatik)  

Vortragender: Michael Rathjen (Leeds), Moderation: C. Gaßner.

Forschungsschwerpunkte (Logik und Theoretische Informatik)

1) Berechenbarkeit über algebraischen Strukturen

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

2) Prädikatenlogik zweiter Stufe

  • Modelle, Henkin-Strukturen zweiter Stufe 

3) Das Auswahlaxiom

Vorträge und Konferenzen

2022  MCU 2022 (Mitglied des Programmkomitees), DMV Annual Meeting 2022 (C. Gaßner: Second-Order Logic and Russell's Axiom of Choice),  CL 2022  (C. Gaßner: Second-Order Henkin Semantics and the Axiom of Choice)

2021 CSL 2021 (Gaßner, Arno Pauly und Florian Steinberg: Computing Measure as a Primitive Operation in Real Number Computation, Proceedings)

2019 Institut für Philosophie, Greifswald:  C. Gaßner. Das Auswahlaxiom und die Prädikatenlogik zweiter Stufe

2017  Arbeitstreffen 2017 (Folien)  

2017  CCA 2017 (Gaßner,  Arno Pauly und Florian Steinberg: Computing measures as a primitive operation, Proceedings, siehe auch Preprint 1 2017)

2016  Colloquium Logicum 2016 (BSS RAM's with ν-Oracle and the Axiom of Choice, Folien)

2016  Arbeitstreffen 2016 (Folien)

2015 CCC 2015

2015  CCA 2015 (Folien - gekürzte Fassung)

2013 Greifswald 2013 (Habilitationskolloquium)

2012  Arbeitstreffen 2012,  CCA 2012,   CCC 2012 (Folien)

2011  Arbeitstreffen 2011,  CCA 2011 (Folien)

2010  Arbeitstreffen 2010,  Greifswald 2010,  Siegen 2010 (Kolloquium),  Bonn 2010 (Kolloquium)

2009 CCA 2009 (Folien),  CiE 2009 (Folien),  CCC 2009 (Folien)

2008 CCA 2008 (Folien),  CiE 2008 (Folien),  Greifswald 2008 (Kolloquium),  Siegen 2008 (Kolloquium)

2007... CiE 2007 (Folien),   CiE 2006,  EPIT 2005,   Greifswald 2005 (Kolloquium),  Dagstuhl 2004 ...

Organisierte Arbeitstreffen und Workshops

Arbeitstreffen 2023  Logic and Gentzen

Arbeitstreffen 2017  Computability and Reducibility

Arbeitstreffen 2016  Computability and the BSS model

Arbeitstreffen 2014  Computability and Logic

Arbeitstreffen 2013  Computability and Logic

Arbeitstreffen 2012  Computability and Logic

Arbeitstreffen 2011  Different models of computation

Arbeitstreffen 2010  Real Computation and BSS Complexity

Special Session 2010  Complexity in Arbitrary Structures

Workshop 2010 Logical Approaches to Barriers in Computing and Complexity im Alfried Krupp Wissenschaftskolleg (Abstract Booklet)

Organisierte Kolloquien und andere Vorträge

Juli 2023: Michael Rathjen: Unabhängigkeitsbeweise: Gentzen, Goodstein und danach

Juni 2017: Florian Steinberg. Berechenbare Analysis und Weihrauch-Reduktionen (weitere Informationen)

November 2016: Rupert Hölzl. Absolutely undecidable sets (Folien, weitere Informationen)

August 2016: André Nies. Randomness and quantum computation

August 2013: Xizhong Zheng. On the Computable Curves

Juli 2013: Robert Rettinger. Komplexitätstheorie in der Analysis

Juli 2012: Dieter Spreen. An isomorphism theorem for partial numberings

Juli 2010: Russell Miller. Factoring Polynomials and Finding Roots

Februar 2010: Johann Makowsky. Das Spektrumproblem von H. Scholz und G. Asser: Ein halbes Jahrhundert danach (im Alfried Krupp Wissenschaftskolleg)

Die Schwerpunkte der Arbeitstreffen

Themen für Bachelor-, Master- und Doktorarbeiten

Falls Sie Interesse an einem Thema zu folgenden Schwerpunkten haben, dann wenden Sie sich bitte an: gassnercuni-greifswaldde.

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
  • Verwandte Themen, siehe dazu auch: T. Zerjatke: Möglichkeiten und Grenzen des DNA-Computings im Hinblick auf PSPACE (Diplomarbeit)

    Themen, die in der Vergangenheit bearbeitet wurden und ebenfalls weiter bearbeitet werden können:

    • Verschiedene Klassen von Automaten über dem Ring der reellen Zahlen (Masterarbeit)
    • BSS-Automaten über verschiedenen Strukturen (Bachelorarbeit)
    • Deterministische Operatoren in einem uniformen Berechnungsmodell (Bachelorarbeit)
    • usw.

    Zu den aktuellen Themen gehören auch:

    • Mathematische Probleme in der Prädikatenlogik
    • Die Bedeutung des Auswahlaxioms
      • in der Berechenbarkeitstheorie
      • in der Graphentheorie
      • usw.