Christine Gaßner (University of Greifswald) – Abstract computation over first-order structures: Universal BSS RAMs and their complexity

The BSS-RAM model is a logic-based concept that provides a mathematical framework for characterizing algorithms that enable the uniform processing of all finite sequences of individuals in a domain of discourse. The model is machine-oriented and the result of a generalization of several types of abstract machines, such as real RAMs, BSS machines, and deterministic or non-deterministic Turing machines. It was developed on the basis of a concept introduced by Dana Scott and discussed by Egon Börger and others. Individual algorithms can be determined by first-order programs and suitable structures. Each program of a machine is an element of a formal language. Its semantics can be defined by a transition system derived from a suitable first-order structure. The operations of the underlying structure are used to transform objects whereby the transformations themselves can also depend on states and conditions that can be evaluated by means of the relations of the structure.