Computation on Structures - The Challenge of Seamless Integration of Theory and Rigorous Scientific Practice

In 1985 Egon Börger published his influential monograph on computation theory, logic, and complexity (Börger, 1989), which focused on the concept of formal language as a carrier of the precise expression of meaning, facts, and problems, and the concept of algorithm or calculus, i.e., a formally operating procedure for the solution of precisely described questions and problems. At that time, the text was at the forefront of a modern theory of these concepts, paving the way in which they developed first in mathematical logic and computability theory and later in automata theory, the theory of formal languages and complexity theory. Nonetheless, the state of the theory left many open problems. Computing started to stretch out into many new application areas. Distributed computing over networks became possible, database systems facilitated concurrent computation, artificial intelligence ventured from a niche area to a useful technology, enabling inferential problem solving in diagnosis, controlling machines through software became possible, etc.