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

Authors: Jamroga, Wojciech | Konikowska, Beata | Kurpiewski, Damian | Penczek, Wojciech

Article Type: Research Article

Abstract: Some multi-agent scenarios call for the possibility of evaluating specifications in a richer domain of truth values. Examples include runtime monitoring of a temporal property over a growing prefix of an infinite path, inconsistency analysis in distributed databases, and verification methods that use incomplete anytime algorithms, such as bounded model checking. In this paper, we present multi-valued alternating-time temporal logic (mv-ATL → ∗ ), an expressive logic to specify strategic abilities in multi-agent systems. It is well known that, for branchingtime logics, a general method for model-independent translation from multi-valued to two-valued model checking exists. …We show that the method cannot be directly extended to mv-ATL → ∗ . We also propose two ways of overcoming the problem. Firstly, we identify constraints on formulas for which the model-independent translation can be suitably adapted. Secondly, we present a model-dependent reduction that can be applied to all formulas of mv-ATL → ∗ . We show that, in all cases, the complexity of verification increases only linearly when new truth values are added to the evaluation domain. We also consider several examples that show possible applications of mv-ATL → ∗ and motivate its use for model checking multi-agent systems. Show more

DOI: 10.3233/FI-2020-1955

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

Authors: Janicki, Ryszard | Mikulski, Łukasz

Article Type: Research Article

Abstract: Traces and their extensions as comtraces, step traces and interval traces are quotient monoids over sequences or step sequences that play an important role in the formal analysis and verification of concurrent systems. Step traces are generalizations of comtraces and classical traces while interval traces are specialized traces that can deal with interval order semantics. The algebraic structures and their properties as projections, hidings, canonical forms and other invariants are very well established for traces and fairly well established for comtraces. For step traces and interval traces they are the main subject of this paper.

Keywords: traces, interval traces, step traces, partially commutative monoids

DOI: 10.3233/FI-2020-1956

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

Authors: Sanchez Martin, Jose Angel | Petre, Ion

Article Type: Research Article

Abstract: Network controllability focuses on the concept of driving the dynamical system associated to a directed network of interactions from an arbitrary initial state to an arbitrary final state, through a well-chosen set of input functions applied in a minimal number of so-called input nodes. In earlier studies we and other groups demonstrated the potential of applying this concept in medicine. A directed network of interactions may be built around the main known drivers of the disease being studied, and then analysed to identify combinations of drug targets controlling survivability-essential genes in the network. This paper takes the next step and …focuses on patient data. We demonstrate that comprehensive protein-protein interaction networks can be built around patient genetic data, and that network controllability can be used to identify possible personalised drug combinations. We discuss the algorithmic methods that can be used to construct and analyse these networks. Show more

Keywords: Network controllability, personalised medicine, multiple myeloma, mutated genes, essential genes, drug target genes

DOI: 10.3233/FI-2020-1957

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

Authors: Thiagarajan, P. S. | Yang, Shaofa

Article Type: Research Article

Abstract: We present the theory of distributed Markov chains (DMCs). A DMC consists of a collection of communicating probabilistic agents in which the synchronizations determine the probability distribution for the next moves of the participating agents. The key feature of a DMC is that the synchronizations are deterministic, in the sense that any two simultaneously enabled synchronizations involve disjoint sets of agents. Using our theory of DMCs we show how one can analyze the behavior using the interleaved semantics of the model. A key point is, the transition system which defines the interleaved semantics is—except in degenerate cases—not a Markov …chain. Hence one must develop new techniques to analyze these behaviors exhibiting both concurrency and stochasticity. After establishing the core theory we develop a statistical model checking procedure which verifies the dynamical properties of the trajectories generated by the the model. The specifications consist of Boolean combinations of component-wise bounded linear time temporal logic formulas. We also provide a probabilistic Petri net representation of DMCs and use it to derive a probabilistic event structure semantics. Show more

DOI: 10.3233/FI-2020-1958

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

Authors: Verbeek, Fons J. | Cao, Lu

Article Type: Research Article

Abstract: Biology is 3D. Therefore, it is important to be able to analyze phenomena in a spatiotemporal manner. Different fields in computational sciences are useful for analysis in biology; i.e. image analysis, pattern recognition and machine learning. To fit an empirical model to a higher abstraction, however, theoretical computer science methods are probed. We explore the construction of empirical 3D graphical models and develop abstractions from these models in L-systems. These systems are provided with a profound formalization in a grammar allowing generalization and exploration of mathematical structures in topologies. The connections between these computational approaches are illustrated by a …case study of the development of the lactiferous duct in mice and the phenotypical effects from different environmental conditions we can observe on it. We have constructed a workflow to get 3D models from different experimental conditions and use these models to extract features. Our aim is to construct an abstraction of these 3D models to an L-system from features that we have measured. From our measurements we can make the productions for an L-system. In this manner we can formalize the arborization of the lactiferous duct under different environmental conditions and capture different observations. All considered, this paper illustrates the joint of empirical with theoretical computational sciences and the augmentation of the interpretation of the results. At the same time, it shows a method to analyze complex 3D topologies and produces archetypes for developmental configurations. Show more

Keywords: L-system, Phenotype analysis, Center-line topology, lactiferous duct, 3D model representation

DOI: 10.3233/FI-2020-1959

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