Research Group Theory of Computability over Algebraic Structures

Contact Information

PD Dr. Christine Gaßner

Institute of Mathematics and Computer Science

(Institut für Mathematik und Informatik)

Walther-Rathenau-Straße 47

17489 Greifswald


Phone  +49 3834 420 4610

Telefax + 49 3834 420 4640




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.   


Now online available:  Gaßner: Das Auswahlaxiom im Prädikatenkalkül zweiter Stufe (The Axiom of Choice in the Second-Order Logic), Dissertation, 1984, pdf)


Visit at Jiangsu University (2018)


MCU 2018  (Program Committee Member)


Dagstuhl Seminar 18361

Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (2018)


C. Gaßner: Computation over Algebraic Structures and a Classification of Undecidable Problems.
Math. Struct. in Comp. Science (2017), vol. 27, pp. 1386–1413.

Available on CJO 2016 doi:10.1017/S0960129516000116 (Online: MSCS)


Working meeting (06 - 11  August 2017)

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

See also Preprint 2 2017.


CCA 2017 (Talk)

Christine Gaßner, Arno Pauly, and Florian Steinberg: Computing measures as a primitive operation (Proceedings)

See also  Preprint 1 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)



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. 


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: gassnercuni-greifswaldde.

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