Research Group Theory of Computability over Algebraic Structures

Contact Information

PD Dr. Christine Gaßner

Institut für Mathematik und Informatik

Walther-Rathenau-Straße 47

17489 Greifswald

Phone  +49 3834 420 4610

Telefax + 49 3834 420 4640

gassnerc(at)uni-greifswald(dot)de

 

 

The Theory of Computability over Algebraic Structures is essentially a branch of mathematical logic which is related to theoretical computer science. It deals with different models of computation, where operations of algebraic structures are permitted, and includes generalizations of the classic recursion theory.   


News

Working meeting (06 - 11  August 2017)

The meeting "Computability and Reducibility" took place in Kloster on the island Hiddensee. 

See also Preprint 2 2017.

 

New Preprint

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

Preprint-Reihe Ag Berechenbarkeitstheorie über algebraischen Strukturen Greifswald,

Preprint 1 2017  (First Version 3 April 2017).

 

Colloquium (07 November 2016, 4.00 pm)

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

more

 

Colloquium Logicum 2016 (September 2016)

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

 

Colloquium on Hiddensee (09 August 2016, 1.00 pm)

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

 

Working meeting (08 - 12  August 2016)

The meeting "Computability and the BSS-Model" took place in Kloster on the island Hiddensee. 

 

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


Research

Research Areas

  • Computability over Algebraic Structures
  • Classification of algebraic problems according to their degree of undecidability
  • Bounds of Complexity and P-NP-problems
  • The BSS-RAM model and Moschovakis operators (definitions)

See also (in german):

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

Topics for Bachelor, Master and PhD thesis

If you are interested in writing a thesis in any of the following topics, please contact: gassnerc(at)uni-greifswald(dot)de.

Main Topics:

  • The power of models of computation between finite automata and BSS-RAM's over algebraic structures. This topic was proposed at a working meeting 2014. The aim is to collect application examples and to compare different types of automata as well as to prove the power of individual types of automata and the insolubility of problems by certain automata. 
  • Classification of currently avaliable  models of computation
  • The significance of the axioms of choice 
    • in Theory of Computability
    • in Graph Theory
    etc.