Bio

Tommaso Bolognesi obtained his laurea in physics from Pavia University (Italy) in 1976, and his M.S. in computer science from the University of Illinois in 1982. He is currently senior researcher at ISTI-CNR, an Institute of the Italian National Research Council at Pisa. His initial research interest was the application of stochastic processes and fractals to computer music composition. He then moved to formal specification and verification of concurrent systems, and contributed to the definition of the LOTOS specification language (an ISO standard). Later on he has worked on timed extensions of process algebra, on the relations between graphical and algebraic representations of process networks, on specification styles based on constraint composition, on their application to various classes of languages, on the unification of event-based and state-based paradigms. He teaches software engineering at the University of Siena, and is a member of the program committee of several conferences on formal methods.

Project: Petri Net Landscapes and Beyond

Petri nets are a graphical formalism for describing concurrent systems, in which nondeterminism, independence, sequentiality/causality, and synchronization among events are regarded as important aspects of behaviour. Petri nets can be understood as a generalization of interacting finite state machines, and may indeed exhibit infinite states. Process algebras also model concurrent systems, but offer the advantages of algebraic manipulation and elegant formal semantics. In their basic form, Petri nets are known not to be Turing powerful, but simple extensions are sufficient to immediately reach full theoretical expressive power.

In the first part of my project I investigated, in NKS style, the “versatility” of plain Petri nets (often called place/transition nets), in search of some graphical evidence of their intermediate position between finite-state and Turing machines. This implies enumerating them, and devising a way to let their computations generate two-dimensional patterns. Inspiration is drawn from the experiments at pp. 608–609 of the NKS book, where the relation between finite-state computations and nested behaviours is given an effective pictorial representation. An interesting difference between these (special) finite-state machines and Petri nets is that the latter may not be always ready to accept an input symbol. This fact triggers interesting questions on the final shapes of the reachable portions of the canvas. Furthermore, various criteria may be explored for associating a color to the final state of Petri net computation (if any). Color ranges of unbounded size are quite plausible, in light of the potential unbounded growth of tokens circulating in the net.

In the second part of my project, I explored this technique with process-algebraic expressions, and conducted NKS-style experiments meant to expose the complexity of various small sets of process-algebraic operators. At a syntactic level, process-algebraic expressions are similar to Mathematica expressions, and have a tree structure. At the semantic level, they denote behavior trees (nondeterministic computations) in which arcs are labeled by instantaneous, atomic events. The canvas method seems less effective for process algebras.

Favorite Four-Color, Nearest-Neighbor, Totalistic Rule

Rule chosen: Rule chosen: 810308

I like this one because of the vertical flowing stripes, similar to rivers that persist in preserving the separation of their waters, perhaps of different temperatures, when sharing the same bed.