On the Two Worlds of Carl Adam Petri’s Nets

Abstract

The author describes meetings with Carl Adam Petri which revealed his universal mind, ranging from very detailed knowledge of physics through mathematical skills to formal reasoning about communication disciplines.

With his work Carl Adam Petri initiated a scientific world that includes by now a huge number of publications. The area covers multiple aspects, but from a historical point of view there have been two main streams or worlds of thinking. This article describes how I experienced both of these worlds of working and thinking in over 40 years of my academic life.

During the last year of my academic studies toward a degree in mathematics in 1971 at the University of Bonn I was employed as a student assistant at a major research institution near Bonn, the Gesellschaft für Mathematik und Datenverarbeitung (GMD), where Petri was the director of the Institute for Information Systems. As a student I saw Petri only from a distance, but I attended the Ph.D. Defense of Hartman Genrich, where he emphasized Petri nets as the description model of the future in contrast to the old-fashioned “steam engine” of automata theory (a field in which I was writing my diploma thesis). This experience motivated me to change my research interests to Petri nets after having finished my Ph.D. thesis on topological automata in 1974 at the University of Hamburg.

Following my education at the University of Bonn (and not at the GMD) my research on Petri nets started in the context of finite automata and formal languages, and my first major publication in this field was on “Regular Petri Net Languages” [22]. Such a publication would not have been possible within Petri’s research group. Petri always emphasized the point that modeling should be in direct accordance with physical laws and real-world observations. As a consequence, for example, multiple tokens were not used, and side conditions or token capacities for example were not considered. This was motivated by the requirement of “good modeling,” but examples of such modeling had rarely been published at that time. The entire universe was conceived as a net, while we were working with small cutouts. Here I cannot describe this way of thinking in detail, but will subsume it under the heading of “General Net Theory (GNT).” At conferences, the GNT point of view has been advocated by the members of the Petri school in such a way that P. S. Thiagarajan was reported to call it the “Petri church.”

This was in contrast to the way Petri nets were treated outside the GMD group, where a model or a way of modeling was not a priori considered to be “good” or “bad,” instead, any formalism was worth studying. The value of such formalisms was determined by the way they fitted into the general framework of theoretical informatics or by their usefulness in applications. Here, I will call that world the “World of the Free Petri Net (FPN).”¹ These two worlds, GNT and FPN, were even distinguishable by the way nets were depicted: transitions were represented by simple bars in FPN, but by small boxes in GNT.

In 1976 I spent a research visit at the University Paris 6, invited by Claude Girault. There I met a young generation of Petri net researchers who became well known in the research community some years later (G. Roucairol, G. Memmi, G. Berthelot, G. Vidal-Naquet, and others). I remember the following scene describing the state of Petri net research at that time. As my first foreign language in high school had been French, I wanted to give my introductory talk on Petri nets in French. At that time no publication in French on the topic was known (at least to me). Therefore I had to learn the key notions (such as “firing a transition”) from my French colleagues just before the talk. Vice versa, papers on place invariants (e.g., by K. Lautenbach and H. Genrich) were available only in German. Therefore these French colleagues were strongly interested in translating them into the French language. During a later visit Claude Girault made the proposal to create a workshop organized by France and Germany. Following this proposal we organized the “First European Workshop on Application and Theory of Petri Nets” in 1980 [3] in Strasbourg. It became a series, later under the name of a conference.²

In 1978 I had a contribution at a conference in Zakopane, Poland, where I presented an extension of ordinary Petri nets that I called “Self-modifying Nets” [17]. But although (or because?) the model was inspired by a paper of H.E. Fuss from GMD, there was a critical comment by Petri himself saying that my definitions were not formally correct. At that time, I found this criticism rather strange since my argumentation was strictly formal, contrary to Petri’s papers, which did not follow the mathematical style with definitions, theorems, and proofs. Today, I think that Petri’s criticism came from his convictions with respect to modeling principles; e.g., in this case, graphical representations of Self-modifying Nets violated the principle of locality. My interest in using this formalism was to investigate the Turing completeness of different extensions of Petri nets, as Self-modifying Nets contain inhibitor nets, reset nets, etc. as subclasses.³

In the year 1979 Wilfried Brauer in cooperation with Carl Adam Petri and Brian Randell organized the Advanced Course “Net Theory and Applications” at the University of Hamburg [1]. At that time, due to external constraints, the two worlds of GNT and FPN were obliged not only to meet, but to coordinate their concepts and definitions. This had already happened at a meeting at the GMD some time before the Advanced Course started. The representatives of both worlds were (symbolically) sitting face to face on the two sides of a large table and had intense discussions about the topics to be presented, about the lectures to be held and the definitions to be used. For example, an agreement was reached to call a net with multiple tokens on places and arc weights a Place Transition Net, whereas the favorite model of the GNT world was called a Condition Event Net. The conference itself was a highlight in the history of Petri net development, and I had the pleasure to be the chairman of Petri’s lecture. Researchers and students from all over the world attended,⁴ and when walking downtown in a guided tour, participants where amused to see a physical (St.) Petri church in red-brick Gothic style.

The power of modeling with Petri nets came to my attention more strongly than ever before when, with Eike Jessen as co-author, I developed a new course bringing together topics from classical books on operating systems, concurrency, and queueing theory. Here I was able to design convincing net models for many classical examples found in those books. The course was later published by Springer [6]. Much of the material was also used in the five chapters I contributed to a book that was the outcome of a European project [4]. In the context of the first of these two books a certain modeling problem appeared, namely that tasks or programs are moving and changing objects in a (queueing) system. This had been the motivation for the more elaborate Petri net formalism of Object Systems first published in 1991 [18] and described in more detail in [19]. Later on, in a personal letter Petri appreciated this development. An important result of this work was the development of the Petri net tool Renew by Kummer [9], Daniel Moldt, and others, which is able to model place/transition nets as well as coloured nets, object nets, and object-oriented nets, all addressed by the reference nets formalism. The work with this tool is still important and has produced complex multi-agent systems and support for collaborative software engineering [14].

In 1988 Carl Adam Petri became a professor at the University of Hamburg. The proposal for this appointment was made by Hermann Flessner, who had been in contact with Konrad Zuse and Petri some years before at Hannover. As the responsible professor I had to initiate the necessary decisions at the Institute of Informatics, the University and the Government [2]. As a consequence, for many years Petri regularly gave lectures and guided seminars and research groups on topics of his choice. This way we learned his way of thinking and obtained a better understanding of the results of his research, many of which were (and still are) not available in the literature. Notorious were the long sessions until late at night with discussions on the topics of the day’s lecture given by Carl Adam, ignoring lunch and dinner breaks in a room full of smoke (see the picture Fig.1, designed by Carl Adam himself). He loved these meetings with students very much as he didn’t have that kind of environment for discussions at the GMD institute.

Fig. 1

Hold up high the torch of political correctness

Among the student participants the core group included Uwe Fenske, Stefan Haar, Peter Langner, Hartmut Müller, and Mark-Oliver Stehr⁵ who were regularly joined by several student and research staff members of the university and, in particular, by our theory group. While attempting to absorb as much as possible of Petri’s ideas, they especially dealt with concurrency theory and cycloids. On the occasion of this article, from their many notes Uwe Fenske gave me the following two of Petri’s statements (originally in German): May 25, 1990: “Electron orbitals are nothing else than four dimensional cycloids” and May 30, 1990: “Parallel computing via informatics achieves more than sequential computing, which is still denied by theoretical computer scientists today.”

Petri’s approach encouraged them to apply his ideas to other disciplines, “such as linguistics. Peter Langner developed so-called “ChronoNarratio-Graphs,” which are Petri nets expressing the causality and independence of courses of action in literary texts, as for instance in Tolstoy’s novel “Anna Karenina” [11].

Inspired by long meetings and discussions with C. A. Petri, Mark-Oliver Stehr developed and studied a more general theory of partial cyclic orders that includes cycloids as a special case [16]. He is now a senior scientist at SRI International, Menlo Park, California, and he recently sent me a very enthusiastic letter from Petri, dated March 23, 1997, on Kummer and Stehr’s paper on Petri’s axioms for concurrency [10], which was also a result of Petri’s lectures in Hamburg and Stehr’s investigation of concurrency theory under the guidance of Jozef Gruska. In this letter Petri emphasized the importance of an axiomatic system based on causality and on concurrency relations, the general value of measurement methods for “Rough Sets,” and the notion of coherence in general sciences. When reading the letter now, Stehr said he was surprised that Petri explicitly mentioned Biology, as he himself is working today with biologists at SRI on modeling biological systems. Stehr expects that Petri’s approach to causality, already very closely related to his own current work, might become even more relevant in view of the exponentially increasing flood of experimental/observational data enabled by the latest technologies.

With my colleagues Daniel Moldt and Rolf v. Lüde, a sociologist, I directed some projects to combine the methods from informatics and sociology within a new discipline, called socionics [8]. The goal of these projects was to model theories of the famous sociological schools of Norbert Elias, Pierre Bourdieu, Heinrich Popitz, Niklas Luhmann, and others in such a way that they can be used for the design of computer systems involved in human or quasi-human societies or multi-agent systems. In these modelings, Petri nets have been successfully used. An important idea was to structure nets according to the modeled system. In the context of sociology especially the agent-oriented approach Mulan proved to be very suitable [7]. For one of the books on socionics [23] that documented these results, C. A. Petri wrote a preface, dated December 22, 2002. In this preface he argued that the considerably increased potentials of communication are also influencing sociology. But these effects should not be forced into the “corset” of traditional mathematics or informatics. It is not the precision known from mathematics or physics that is appropriate in such a model, but rather the simplicity and refutation-definiteness to describe the margins (he wrote “Spielräume”) of actors. These margins were limited by causal dependencies or independencies that were more adequate for description than totally ordered time scales of events. Therefore, Petri welcomed the given approach to model parts of sociologic theories by formal theories using net theory.

In 2007 I was asked to chair the Petri net conference 2008 in Xian, China together with Kees van Hee. In a letter dated May 20, 2007 Carl Adam wrote: “I would enjoy very much to fly to China, in particular with you as chairman. However, my age as well as my health do not allow it. But I still think about producing a PPT presentation which you can present.” After some discussions, Kurt Jensen informed me that in order to have a different and shorter contribution than Petri’s presentation at the Miami conference, the steering committee had agreed that I should make such a presentation on the basis of Petri’s proposals as an invited lecture. Following this agreement I decided to make my own presentation, partly using Petri’s slides, and planned to only present material I could clearly understand. This decision was accepted by Carl Adam, but it had the consequence that for a whole year nearly every day I had e-mail exchanges with him to discuss things that were not clear to me. Carl Adam appreciated this procedure since it gave him the opportunity to discuss his ideas, to remove errors, and to find new representations.

The starting point of Petri’s slides was his 3-year collaboration with Konrad Zuse (1910–1995) on the idea of a Computing Universe [12]. They agreed that some of the main tenets of newer physics would have to be expressed, at least those of quantum mechanics and of special relativity. Discussing which tenets should be tackled, Zuse proposed “Those which can be understood by an engineer.” But many years passed before the deterministic approach of the physicist Gerard ’t Hooft (Nobel Prize in 1999) made possible a complete elaboration of the originally conceived ideas.⁶

In the slides Petri follows the principles of combinatorial modeling, which is a proper synthesis of continuous and discrete modeling. Petri gives a reformulation of fundamental physical laws that allows a combinatorial representation. Further important notions are those of slowness, measurement, uncertainty of counting, determinism, and cycloids. Of particular importance for Petri was his discovery that fundamental gates of Boolean circuits, such as XOR-transfer, majority-transfer, or Quine transfer, are topologically equivalent to some of his cycloids. In a recent mail, Mark-Oliver Stehr told me that Petri’s Quine transfer, also known as the Fredkin gate, has now been experimentally realized in quantum computing for the first time by researchers of the Griffith University and the University of Queensland [13].⁷ In the abovementioned personal communication Petri wrote to me: “It is one of my most important concerns to confront the stochastic way of thinking with the combinatorial one. It seems to me that combinatorial results are irrefutable whereas the stochastic view will finally lead to the well-known problems in quantum mechanics.” When my slides⁸ were finished, I asked him in what ways the current presentation was different from the one at the Miami conference. Carl Adam answered: “In Florida, with six hours I had plenty of time. Furthermore, the successful presentation there was a festive experience for me.”

Looking back, the abovementioned contacts with Petri show only a very small part of his entire work. Nevertheless, they document his universal mind, ranging from very detailed physical knowledge through mathematical skills and to formal reasoning about communication disciplines. Coming back to my introduction, two worlds in the field that he established are highlighted in this article: the ordinary one, where most Petri net researchers are working today, modeling systems and proving properties such as liveness, invariants, subclasses, and so on, which is a successor of both the GNT and FPN worlds; and the second world in which Petri seemingly was most interested, namely the foundations of systems compliant with the physical laws of nature, which undoubtedly is GNT.

And there’s me, having started in the FPN world in 1974 and finding myself today partly in the second one, as a wanderer between the worlds, still doing research on Petri’s cycloids [20].