Research Group Theory of Computability over Algebraic Structures
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.
C. Gaßner: Deterministic Operators for BSS RAM's I (extended abstract).
Preprint-Reihe Ag Berechenbarkeitstheorie über algebraischen Strukturen Greifswald,
Colloquium (07 November 2016, 4.00 pm)
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)
- 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.
- 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