This special issue is dedicated to Jetty Kleijn on the occasion of her 65th birthday. Her research is of broad scope. She made significant contributions to a number of research areas both through solving challenging problems and through pioneering new research directions.

She has published influential papers in:

• classical foundations of computer science, in particular in formal languages and automata theory,

• theory of concurrency, in particular in the area of Petri nets, and

• natural computing, in particular in bio-inspired computing and computational modelling of bio-processes.

A considerable part of her research is of an interdisciplinary character. This includes modelling of specific biological processes using approaches already established in computer science (such as Petri nets) as well as investigating novel models of information processing in bio-systems (such as reaction systems).

She has greatly contributed to the development of scientific communities on both the international and the national (local) level. For example, she is a respected community leader in the area of Petri nets and she played a key role in the formation and functioning of the computer science department (Leiden Institute of Advanced Computer Science) at Leiden University, The Netherlands. She is also passionately engaged in promoting the involvement of women in computer science.

Jetty is well-recognised by the scientific community, which was also demonstrated by the enthusiastic response to our invitation to contribute to this special issues, which (after a thorough refereeing process) resulted in the 14 papers that constitute this special issue. They explore a number of research topics that are either directly or indirectly related to research directions pursued by Jetty.

Comparable to going from P/T Petri nets to coloured Petri nets, in “Discovering Object-centric Petri Nets”, van der Aalst and Berti show how to automatically discover object-centric Petri nets from object-centric event logs in order to visualise the complex relationships among objects from different types. Such object-centric event logs can be seen as an intermediate format closer to the actual data collected by today’s information systems. This novel process discovery approach is implemented in the open-source process mining platform PM4Py.

Generalised degenerate (GD) strings are compact representations of sets of similar strings, for which interest has recently grown, as they can be used to represent pan-genomes. In “Comparing Degenerate Strings”, Alzamel et al. present a linear time algorithm for deciding whether two GD strings have a non-empty intersection, even though the intersection of two GD strings can be exponential in the total size of the two strings. They also apply their string comparison tool to devise a simple algorithm to efficiently compute all palindromes in a GD string.

In “Dynamic Exploration of Multi-agent Systems with Periodic Timed Tasks”, Arcile et al. introduce MAPTs, multi-agent systems composed of periodic communicating autonomous agents evolving in a constrained environment, and study methods tailored for efficient model checking. They use an available tool for the high-level Petri net implementation of MAPTs to explore the state space of communicating autonomous vehicle systems. They also compare such explorations with timed automata-based approaches in terms of expressiveness of available queries and computation time.

In “Target-oriented Petri Net Synthesis”, Best et al. categorise various classes of arc-weighted P/T Petri nets with respect to their suitability for being synthesised efficiently from labelled transition systems. As stipulated by applications from hardware design and synthesis, the focus is on efficient synthesis techniques under the additional restriction that the resulting net should be a choice-free Petri net or some specific subclass. This results in a comprehensive comparison of some of the authors’ and their groups’ work over the past few years.

The automated comparison of process models, which are fundamental for precise representations of organisational processes, has received significant attention in the domain of business process management (BPM). In “Flexible Process Model Mapping using Relaxation Labeling”, Carmona et al. present a flexible novel technique for process model mapping, based on the relaxation labelling constraint satisfaction algorithm. Their approach is implemented in the NLP4BPM open platform, providing visualisations of the performed mappings and computed similarity scores.

For some applications of P/T Petri nets it is relevant to know whether a transition of a net is a stop-transition, which is the case if each reachable marking of the net enables only finite occurrence sequences without occurrences of that transition. In “Stop-transitions of Petri Nets”, Desel and Finthammer show how to identify stop-transitions of unbounded nets using coverability graphs. They moreover adapt their technique to more general questions considering sets of transitions and focussing on certain parts of the net. The developed algorithm is implemented in the Cycl↻n tool to visualise relevant behavioural structures.

It is well known that most natural properties of regular languages are algorithmically decidable. In “Roots and Powers in Regular Languages: Recognizing Nonregular Properties by Finite Automata”, Frei et al. provide an example of a natural property with a surprisingly different behaviour, namely a problem that is non-regular yet identifiable by finite automata. Moreover, they prove that the roots of a regular language, while always regular, may have a state complexity that increases exponentially and they provide concrete constructions for upper and lower bounds on this state complexity.

The global dynamics of reaction systems can be represented by (directed) transition graphs that are uniquely determined by so-called 0-context graphs. In “Companions and an Essential Motion of a Reaction System”, Genova et al. consider companion classes of the outsets of a transition graph and introduce an essential motion as a directed multigraph whose vertices are such companion classes. They observe that all reaction systems whose 0-context graphs are associated to a given essential motion have isomorphic transition graphs. As a result, all such 0-context graphs are related by swapping the outgoing edges of companion vertices.

The operation of shuffling (words) has a long history in the theory of formal languages. In “On Shuffling a Word with its Letter-to-Letter Substitution”, Halava et al. consider a kind of self-shuffle with respect to a letter-to-letter morphism, according to which a word is shuffled with its own image under that letter-to-letter morphism. They prove that, given a regular language and a letter-to-letter morphism, it is undecidable whether or not there exists a word such that the intersection of the self-shuffle of that word with respect to the letter-to-letter morphism and the regular language is empty.

Multi-agent scenarios sometimes require the evaluation of specifications in rich domains of truth values. In “Multi-valued Verification of Strategic Ability”, Jamroga et al. present a multi-valued variant of alternating-time temporal logic, in which the truth values are taken from an arbitrary distributive lattice. They show that multi-valued verification can usually be performed by means of efficient (polynomial-time) translations to classical (2-valued) verification. They also present an appealing case study of drones patrolling for pollution in a city that demonstrates the modelling value of their approach and well as its efficiency.

The theory of traces has a long history in concurrency theory and their algebraic structures and properties are well developed. This is not the case for step traces, which are generalisations of classical traces, and neither for interval traces, which are specialised traces for dealing with interval order semantics. In “Algebraic Structure of Step Traces and Interval Traces”, Janicki and Mikulski define and discuss a number of algebraic aspects (focussing in particular on various types of canonical forms and projection representations) of both step traces and interval traces, with the aim of better understanding their mutual relationship.

Precision medicine aims to integrate patient data with genetic knowledge to find suitable personal therapeutic strategies. In “Network Controllability Analysis of Three Multiple-myeloma Patient Genetic Mutation Datasets”, Sanchez Martin and Petre demonstrate the applicability of network controllability for identifying possible personalised drug combination therapies based on directed networks of protein-protein interactions built around patient genetic data. They discuss the algorithmic methods that can be used to construct and analyse such networks.

In “A Theory of Distributed Markov Chains”, Thiagarajan and Yang present a theory of distributed Markov chains, which are networks of sequential agents synchronising on common actions that determine the probabilistic outcomes. Since the transition systems defining their interleaved semantics are generally not Markov chains, they develop novel statistical model-checking procedures to analyse their behaviour exhibiting a mix of concurrency and stochasticity. They also provide a probabilistic Petri net representation and use it to derive a probabilistic event structure semantics.

In “L-systems from 3D-imaging of Phenotypes of Arborized Structures”, Verbeek and Cao explore the use of L-systems to support the analysis of phenotypes in molecular developmental biology in a spatio-temporal manner through the construction of empirical 3D graphical models and abstractions from these models formalised as L-systems. They illustrate their approach with a case study in which they formalise the arborisation of the lactiferous duct in newborn mice as an L-system, and show how this spatial abstraction enables to represent the phenotypical effects from different environmental conditions as observed from experiments.

The editors and contributors to this special issue wish Jetty happiness and satisfaction in both her personal and scientific life.

We thank the authors and the referees for their efforts to produce this special issue. We are grateful to the editor-in-chief of Fundamenta Informaticae, Professor Damian NiwiÂťnski, for the help and support during the editorial process.

Guest editors:

Maurice ter Beek

ISTI–CNR, Pisa, Italy

Maciej Koutny

Newcastle University, Newcastle upon Tyne, United Kingdom

Grzegorz Rozenberg

Leiden University, Leiden, The Netherlands

The University of Colorado Boulder, Boulder, Colorado, USA