Abstract computation over first-order structures: Sufficient conditions for the existence of universal BSS RAMs

Abstract: The BSS-RAM model can be used for characterizing uniform algorithms within a mathematical framework. BSS RAMs over first-order structures are the result of a generalization of various types of abstract machines such as BSS machines and Turing machines. On the one hand, universal machines are not necessary for executing arbitrary programs since any machine has its own program. On the other hand, universal BSS RAMs and, in particular, universal non-deterministic BSS RAMs are helpful in defining complete problems for some classes in different hierarchies of decision problems. Here, we will discuss sufficient conditions for their existence. We will consider first-order structures that contain only a finite number of operations and relations, including or excluding the identity relation, and with or without constants. Christine Gaßner (University of Greifswald)

Short CV: After graduating in mathematics in 1981, Christine Gaßner began to study mathematical logic and work in Günter Asser's research group. In 1985, she received a doctorate degree for her thesis on the axiom of choice in second-order Henkin logic in Greifswald. Since 1993 she has been dealing with abstract computation over various structures. Among other things, she investigated the possibility of constructing structures with P = NP. She completed her habilitation thesis in 2013 and received the venia legendi for mathematics from the University of Greifswald and the facultas docendi for theoretical computer science. From 2015 to 2023, she was the head of the research group Theory of Computability over Algebraic Structures and responsible for the teaching modules in Mathematical Logic and Theoretical Computer Science at the Institute of Mathematics and Computer Science in Greifswald.