Fundamenta Informaticae - Volume 175, issue 1-4

Authors: ter Beek, Maurice | Koutny, Maciej | Rozenberg, Grzegorz

Article Type: Other

DOI: 10.3233/FI-2020-1945

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. v-viii, 2020

Authors: van der Aalst, Wil M.P. | Berti, Alessandro

Article Type: Research Article

Abstract: Techniques to discover Petri nets from event data assume precisely one case identifier per event. These case identifiers are used to correlate events, and the resulting discovered Petri net aims to describe the life-cycle of individual cases. In reality, there is not one possible case notion, but multiple intertwined case notions. For example, events may refer to mixtures of orders, items, packages, customers, and products. A package may refer to multiple items, multiple products, one order, and one customer. Therefore, we need to assume that each event refers to a collection of objects, each having a type (instead of a …single case identifier). Such object-centric event logs are closer to data in real-life information systems. From an object-centric event log, we want to discover an object-centric Petri net with places that correspond to object types and transitions that may consume and produce collections of objects of different types. Object-centric Petri nets visualize the complex relationships among objects from different types. This paper discusses a novel process discovery approach implemented in PM4Py. As will be demonstrated, it is indeed feasible to discover holistic process models that can be used to drill-down into specific viewpoints if needed. Show more

Keywords: Process mining, Petri nets, Process discovery, Multiple viewpoint models

DOI: 10.3233/FI-2020-1946

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 1-40, 2020

Authors: Alzamel, Mai | Ayad, Lorraine A.K. | Bernardini, Giulia | Grossi, Roberto | Iliopoulos, Costas S. | Pisanti, Nadia | Pissis, Solon P. | Rosone, Giovanna

Article Type: Research Article

Abstract: Uncertain sequences are compact representations of sets of similar strings. They highlight common segments by collapsing them, and explicitly represent varying segments by listing all possible options. A generalized degenerate string (GD string) is a type of uncertain sequence. Formally, a GD string Ŝ is a sequence of n sets of strings of total size N , where the i th set contains strings of the same length ki but this length can vary between different sets. We denote by W the sum of these lengths k 0 , k 1 , . . . , k …n -1 . Our main result is an 𝒪(N + M )-time algorithm for deciding whether two GD strings of total sizes N and M , respectively, over an integer alphabet, have a non-empty intersection. This result is based on a combinatorial result of independent interest: although the intersection of two GD strings can be exponential in the total size of the two strings, it can be represented in linear space. We then apply our string comparison tool to devise a simple algorithm for computing all palindromes in Ŝ in 𝒪(min{W , n 2 }N )-time. We complement this upper bound by showing a similar conditional lower bound for computing maximal palindromes in Ŝ. We also show that a result, which is essentially the same as our string comparison linear-time algorithm, can be obtained by employing an automata-based approach. Show more

Keywords: degenerate strings, generalized degenerate strings, elastic-degenerate strings, string comparison, palindromes

DOI: 10.3233/FI-2020-1947

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 41-58, 2020

Authors: Arcile, Johan | Devillers, Raymond | Klaudel, Hanna

Article Type: Research Article

Abstract: We formalise and study multi-agent timed models MAPTs (Multi-Agent with Periodic timed Tasks ), where each agent is associated with a regular timed schema upon which all possible actions of the agent rely. MAPTs allow for an accelerated semantics and a layered structure of the state space, so that it is possible to explore the latter dynamically and use heuristics to greatly reduce the computation time needed to address reachability problems. We use an available tool for the Petri net implementation of MAPTs, to explore the state space of autonomous vehicle systems. Then, we compare this exploration with timed …automata-based approaches in terms of expressiveness of available queries and computation time. Show more

Keywords: Real time multi-agent systems, periodic behaviour, on-the-fly exploration

DOI: 10.3233/FI-2020-1948

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 59-95, 2020

Authors: Best, Eike | Devillers, Raymond | Erofeev, Evgeny | Wimmel, Harro

Article Type: Research Article

Abstract: When a Petri net is synthesised from a labelled transition system, it is frequently desirable that certain additional constraints are fulfilled. For example, in circuit design, one is often interested in constructing safe Petri nets. Targeting such subclasses of Petri nets is not necessarily computationally more efficient than targeting the whole class. For example, targeting safe nets is known to be NP-complete while targeting the full class of place/transition nets is polynomial, in the size of the transition system. In this paper, several classes of Petri nets are examined, and their suitability for being targeted through efficient synthesis from …labelled transition systems is studied and assessed. The focus is on choice-free Petri nets and some of their subclasses. It is described how they can be synthesised efficiently from persistent transition systems, summarising and streamlining in tutorial style some of the authors’ and their groups’ work over the past few years. Show more

Keywords: Choice-freeness, Persistence, Petri Nets, Synthesis

DOI: 10.3233/FI-2020-1949

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 97-122, 2020

Authors: Carmona, Josep | Padró, Lluís | Delicado, Luis

Article Type: Research Article

Abstract: Computing a mapping between two process models is a crucial technique, since it enables reasoning and operating across processes, like providing a similarity score between two processes, or merging different process variants to generate a consolidated process model. In this paper we present a new flexible technique for process model mapping, based on the relaxation labeling constraint satisfaction algorithm. The technique can be instantiated so that different modes are devised, depending on the context. For instance, it can be adapted to the case where one of the mapped process models is incomplete, or it can be used to ground an …adaptable similarity measure between process models. The approach has been implemented inside the open platform NLP4BPM, providing a visualization of the performed mappings and computed similarity scores. The experimental results witness the flexibility and usefulness of the technique proposed. Show more

Keywords: Process modeling, model similarity, graph mapping, relaxation labeling

DOI: 10.3233/FI-2020-1950

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 123-141, 2020

Authors: Desel, Jörg | Finthammer, Marc

Article Type: Research Article

Abstract: A transition t stops a place/transition Petri net if each reachable marking of the net enables only finite occurrence sequences without occurrences of t (i.e., every infinite occurrence sequence enabled at this marking contains occurrences of t ). Roughly speaking, when t is stopped then all transitions of the net stop eventually. This contribution shows how to identify stoptransitions of unbounded nets using the coverability graph. Furthermore, the developed technique is adapted to a more general question considering a set of stop-transitions and focussing on a certain part of the net to be stopped. Finally, an implementation …of the developed algorithm is presented. Show more

Keywords: unbounded Petri nets, coverability graphs, termination of Petri nets, stop-transitions, minimal coverability sets

DOI: 10.3233/FI-2020-1951

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 143-172, 2020

Authors: Frei, Fabian | Hromkovič, Juraj | Karhumäki, Juhani

Article Type: Research Article

Abstract: It is well known that the set of powers of any given order, for example squares, in a regular language need not be regular. Nevertheless, finite automata can identify them via their roots. More precisely, we recall that, given a regular language L , the set of square roots of L is regular. The same holds true for the nth roots for any n and for the set of all nontrivial roots; we give a concrete construction for all of them. Using the above result, we obtain decision algorithms for many natural problems on powers. For example, …it is decidable, given two regular languages, whether they contain the same number of squares at each length. Finally, we give an exponential lower bound on the size of automata identifying powers in regular languages. Moreover, we highlight interesting behavior differences between taking fractional powers of regular languages and taking prefixes of a fractional length. Indeed, fractional roots in a regular language can typically not be identified by finite automata. Show more

DOI: 10.3233/FI-2020-1952

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 173-185, 2020

Authors: Genova, Daniela | Hoogeboom, Hendrik Jan | Jonoska, Nataša

Article Type: Research Article

Abstract: For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with …isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices. Show more

Keywords: directed graphs, graph isomorphism, graphs on posets, dynamics of reaction systems, equivalence of reaction systems

DOI: 10.3233/FI-2020-1953

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 187-199, 2020

Authors: Halava, Vesa | Harju, Tero | Sahla, Esa

Article Type: Research Article

Abstract: Denote by ш the operation of interleaving, or shuffling, of words. We prove that, given a regular language R and a letter-to-letter morphism φ , it is undecidable whether or not there exists a word ω such that ω ш φ (ω ) ∩ R ≠ ø.

DOI: 10.3233/FI-2020-1954

Citation: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 201-206, 2020