In Memory of Steffen Hölldobler: From Logic to Formal and Cognitive Reasoning

After pursuing a Diploma in Computer Science, Steffen happened to quit the Army and start as a research and teaching assistant at the University of the Bundeswehr Munich with Prof. Niegel, where UF was working as a postdoc. During his time as a PhD student Steffen started as a visiting research associate at Alan Robinson’s Logic Programming Research Group at the Syracuse University, USA in 1983. During this visit he became interested in the combination of logic and functional programming—a topic that paved the way for a very fruitful collaboration between Steffen and UF (e.g. [8]). Figure 1 shows an example: there is a logic program PYTHAGORAS which uses a function \(*\) for multiplication. During execution of the program it might happen that the arguments of the function are not yet instantiated, such that the function cannot be evaluated; in such a case the unification algorithm uses an equivalent logic program, in our example the clauses for MULT, to further evaluate the function call.

For his PhD-Thesis Steffen concentrated on Equational Logic Programming and his Dissertation was published in the prestigious Springer series Lecture Notes in AI [12]. Figure 2 shows an example from his thesis. It depicts a logic program which contains Horn clauses together with Horn equality theories, and which has to be evaluated by EP-resolution based on EP-unification.

In 1988 Steffen joined Wolfgang Bibel’s Intellectics Group at TU Darmstadt in Germany and shortly thereafter, in 1989, he was offered a one-year fellowship as a postdoc at the International Computer Science Institute (ICSI) at Berkeley, USA. During this period he still remained true to his theme of equational logic programming. There he was introduced to connectionism by Jerry Feldman and he immediately realised that this method could be used excellently for calculating unifiers. Steffen managed to find a clever representation of terms and the unification problem in order to efficiently use networks for computation. Figure 3 shows an example of the representation of two terms from [13].

UF very well remembers the discussion about whether this approach could be regarded as cognitively motivated or whether it was just a clever “hardware trick”. Anyhow, this research at the ICSI finally led to a postdoctoral thesis (Habilitation) on Automated Inferencing and Connectionist Models in 1993. Steffen worked on his thesis at TU Darmstadt with Wolfgang Bibel and Larry Feldman as supervisors. Later on in a series of papers beginning in 2000 he started discussing the problem of combining connectionist-based approaches with symbolic reasoning. In [1] he discussed questions like “how can first-order rules be extracted from a connectionist network?” or “how can established learning algorithms such as backpropagation be combined with symbolic knowledge representation?”—and yes, these are exactly the topics which are nowadays discussed in order to find a way towards explainable AI! All of this can certainly be viewed as Steffen’s first turn towards the field of cognitive science. In later years this aspect becomes much clearer and even more prominent in his work.

Another continuation of Steffen’s earlier work on unification theory can be traced in his work on planning—shortly after joining Wolfgang Bibel’s Intellectics group in 1988 Steffen came across various planning approaches. Together with Josef Schneeberger, he developed a new calculus for deductive planning [17]. The basis for this approach are equational logic programs [12], where situations, which depict states of the world, and plans, which are sequences of actions that transform one situation to another, are represented by terms. Reasoning about situations and plans are performed at the object level and a generated plan precisely corresponds to the well-known concept of a computed answer substitution via SLDE-resolution [9, 12].

As a small example let us consider a situation, where a robot is holding a block v, denoted by h(v), and it is required to perform the action of putting v down on a table surface t, denoted by \(putdown(v)\). Figure 4 shows the definition of the \(putdown\)-operator.

If there is a plan or a sequence of actions whose execution leads to a situation where the robot is holding a block v, then we execute a plan involving the action \(putdown\), which results in the block v being on the table with its top clear and the robot’s hands empty. Analogously, \(z \circ t(v) \circ c(v) \circ e\) is a term representing a situation where t(v) denotes that the block v is on the table t, c(v) denotes that the top of v is clear, and e denotes that the robot’s hands are empty. And \(p: putdown (v)\) is a term denoting a plan p with the additional action of putting v down.

This approach was further developed by Steffen and other members of the Darmstadt Intellectics Group [10, 11, 14, 18]. In particular, Steffen’s cooperation with Michael Thielscher was most successful. The work addresses fundamental AI problems like the frame and the ramification problem. It also considers different types of logic, e.g. linear logic, and alternative proof procedures. Today the approach is known as the fluent calculus [29, 30] and is considered to be one of the most important approaches in the field of reasoning about situations, actions, and causality.

During his time with Wolfgang Bibel’s Intellectics group Steffen was extremely productive. He published in several different areas of AI, e.g. [2, 3], and certainly contributed significantly to the high international reputation of the field of Intellectics at TU Darmstadt.

Steffen became a Professor for Knowledge Representation and Reasoning at the Computer Science Department of Technische Universität Dresden in 1993. In 1997 he established the “International Master’s programme in Computational Logic (MCL)", which was one of the first English-language Master’s programmes at a computer science faculty in Germany and thus garnered a lot of attention for computer science at TU Dresden.

The “European Master’s Program in Computational Logic”, established under his leadership in 2004, expanded the previous programme concept [31]. Besides Dresden as a coordinating university the following partners participated: Free University of Bozen-Bolzano in Italy, Universidade Nova de Lisboa in Portugal, Technische Universität Wien in Austria and NICTA in Australia. In 2003, Steffen founded the International Center for Computational Logic (ICCL) as an international competence centre for research and teaching in the field of computational logic. He was also committed to the faculty as Dean of Studies for international degree programmes. He was the coordinator of both programmes until 2019 and raised a large number of Erasmus scholarships. In the period between 2010 and 2014, the two programmes were supplemented by the DAAD-funded “International PhD Program in Computational Logic” through his initiative.

Steffen organised numerous international summer schools for students both at TU Dresden and in Vietnam, Indonesia, Thailand and Mongolia, among others. These Asian summer schools lasted 2 weeks each, during which a group of German colleagues taught students. During this time Steffen’s many talents became apparent. Organisation in an Asian country was certainly not always easy but Steffen managed to organise everything with remarkable ease. Not only did he enjoy organising the course, but he was also enthusiastic to teach and got the participants excited about Computational Logic. Whenever possible, the lecturers also attended the courses of their colleagues and this helped develop a special relationship among them during the time spent at the summer schools. The many weeks UF was able to spend during these occasions are certainly among his fondest memories.

During the Mongolian summer school MB accompanied the team as a student assistant. At that time she was pursuing a master’s degree in Computational Logic at TU Dresden and met Steffen through his formidable logic lectures. The trip to Mongolia left a lasting impression in MB’s mind and she looks back at them with immense fondness and gratitude to this day. Steffen had been her friend, philosopher and guide ever since and played a very important role in her life.

As mentioned earlier, Steffen already had points of contact with Cognitive Science through his involvement with Connectionism. Also the discussions in the Darmstadt Intellectics group about Johnson Laird’s work on deduction, after the publication of [20], made him familiar with the subject area.

How humans reason has been a long standing question in psychology and cognitive science, with many paradigms attempting to explain and put together pieces of the extraordinary puzzle. Following psychologist Philip Johnson Laird in [19] Steffen too began considering the question “are there general ways of thinking that humans follow when they make deductions?”. Given his background in mathematics and computational logic, Steffen’s preliminary attempt was to consider classical two-valued logic—what was once considered a normative theory for many accounts of human reasoning. However, many studies over the past years have continuously challenged this view [24]. In similar vein, Steffen and his colleagues started exploring the three-valued non-monotonic logic paradigm to model human reasoning and thus began the development of the Weak Completion Semantics.

Steffen’s broad long term research goal was to develop a computational and comprehensive (cognitive) theory for adequately modelling human reasoning tasks. He envisioned the theory to be computational such that human responses to a reasoning task may be computed, and comprehensive such that the theory may be able to encompass a wide variety of tasks. The Weak Completion Semantics is based on ideas initially proposed by Keith Stenning and Michiel van Lambalgen in [28]. It is mathematically sound [16], has been applied to various human reasoning tasks such as the suppression task [6], the selection task [7], the belief-bias effect [25], ethical decision-making [15] etc. It has outperformed the twelve cognitive theories considered by Philip Johnson-Laird and Sangeet Khemlani [21] in syllogistic reasoning [5] and is implementable in a connectionist setting [27].

Until his untimely demise in 2023, Steffen had authored four monographs, more than 100 scientific articles and edited more than 30 publications. Besides his own research, Steffen had also been very active in his academic community, organising workshops and conferences and serving for many years on the selection committee for the GI Doctoral Award. He held a honorary professorship from Stavropol university, but at the same time was horrified by the recent Russian war of aggression in Ukraine. One of his last activities before he fell ill was an attempt to organise a scientific event in parallel to the 17th annual G20 summit in November 2022 in Bali in order to demonstrate peaceful and friendly coexistence among scientists across all borders.

Indeed, the authors will terribly miss their dear friend and bid him a very fond farewell.