Search

In process discovery, the goal is to find, for a given event log, the model describing the underlying process. While process models can be represented in a variety of ways, Petri nets form a theoretically well-explored description language and are therefore often used. In this paper, we extend the eST-Miner process discovery algorithm. The eST-Miner computes a set of Petri net places which are considered to be fitting with respect to a certain fraction of the behavior described by the given event log as indicated by a given noise threshold. It evaluates all possible candidate places using token-based replay. The set of replayable traces is determined for each place in isolation, i.e., these sets do not need to be consistent. This allows the algorithm to abstract from infrequent behavioral patterns occurring only in some traces. However, when combining places into a Petri net by connecting them to the corresponding uniquely labeled transitions, the resulting net can replay exactly those traces from the event log that are allowed by the combination of all inserted places. Thus, inserting places one-by-one without considering their combined effect may result in deadlocks and low fitness of the Petri net. In this paper, we explore adaptions of the eST-Miner, that aim to select a subset of places such that the resulting Petri net guarantees a definable minimal fitness while maintaining high precision with respect to the input event log. Furthermore, current place evaluation techniques tend to block the execution of infrequent activity labels. Thus, a refined place fitness metric is introduced and thoroughly investigated. In our experiments we use real and artificial event logs to evaluate and compare the impact of the various place selection strategies and place fitness evaluation metrics on the returned Petri net. [ABSTRACT FROM AUTHOR]

Metaheuristics are commonly employed as a means of solving many distinct kinds of optimization problems. Several natural-process-inspired metaheuristic optimizers have been introduced in the recent years. The convergence, computational burden and statistical relevance of metaheuristics should be studied and compared for their potential use in future algorithm design and implementation. In this paper, eight different variants of dragonfly algorithm, i.e. classical dragonfly algorithm (DA), hybrid memory-based dragonfly algorithm with differential evolution (DADE), quantum-behaved and Gaussian mutational dragonfly algorithm (QGDA), memory-based hybrid dragonfly algorithm (MHDA), chaotic dragonfly algorithm (CDA), biogeography-based Mexican hat wavelet dragonfly algorithm (BMDA), hybrid Nelder-Mead algorithm and dragonfly algorithm (INMDA), and hybridization of dragonfly algorithm and artificial bee colony (HDA) are applied to solve four industrial chemical process optimization problems. A fuzzy multi-criteria decision making tool in the form of fuzzy-measurement alternatives and ranking according to compromise solution (MARCOS) is adopted to ascertain the relative rankings of the DA variants with respect to computational time, Friedman's rank based on optimal solutions and convergence rate. Based on the comprehensive testing of the algorithms, it is revealed that DADE, QGDA and classical DA are the top three DA variants in solving the industrial chemical process optimization problems under consideration. [ABSTRACT FROM AUTHOR]

In the paper we define three new complexity classes for Turing Machine undecidable problems inspired by the famous Cook/Levin's NP-complete complexity class for intractable problems. These are U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. In the paper, in the spirit of Cook/Levin/Karp, we started the population process of these new classes assigning several undecidable problems to them. We justify that some super-Turing models of computation, i.e., models going beyond Turing machines, are tremendously expressive and they allow to accept arbitrary languages over a given alphabet including those undecidable ones. We prove also that one of such super-Turing models of computation - the $-Calculus, designed as a tool for automatic problem solving and automatic programming, has also such tremendous expressiveness. We investigate also completeness of cost metrics and meta-search algorithms in $-calculus. [ABSTRACT FROM AUTHOR]

This paper studies the algorithms for the minimisation of weighted automata. It starts with the definition of morphisms — which generalises and unifies the notion of bisimulation to the whole class of weighted automata — and the unicity of a minimal quotient for every automaton, obtained by partition refinement. From a general scheme for the refinement of partitions, two strategies are considered for the computation of the minimal quotient: the Domain Split and the Predecesor Class Split algorithms. They correspond respectivly to the classical Moore and Hopcroft algorithms for the computation of the minimal quotient of deterministic Boolean automata. We show that these two strategies yield algorithms with the same quadratic complexity and we study the cases when the second one can be improved in order to achieve a complexity similar to the one of Hopcroft algorithm. [ABSTRACT FROM AUTHOR]

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph G = (V(G), E(G)), a set M ⊆ V(G) is a distance-edge-monitoring set if for every edge e ∈ E(G), there is a vertex x ∈ M and a vertex y ∈ V(G) such that the edge e belongs to all shortest paths between x and y. The smallest size of such a set in G is denoted by dem(G). Denoted by G – e (resp. G\u) the subgraph of G obtained by removing the edge e from G (resp. a vertex u together with all its incident edges from G). In this paper, we first show that dem(G – e) – dem(G) ≤ 2 for any graph G and edge e ∈ E(G). Moreover, the bound is sharp. Next, we construct two graphs G and H to show that dem(G) – dem(G\u) and dem(H \ v) – dem(H) can be arbitrarily large, where u ∈ V(G) and v ∈ V(H). We also study the relation between dem(H) and dem(G), where H is a subgraph of G. In the end, we give an algorithm to judge whether the distance-edge-monitoring set still remain in the resulting graph when any edge of a graph G is deleted. [ABSTRACT FROM AUTHOR]

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph G = (V(G), E(G)), a set M ⊆ V(G) is a distance-edge-monitoring set if for every edge e ∈ E(G), there is a vertex x ∈ M and a vertex y ∈ V(G) such that the edge e belongs to all shortest paths between x and y. The smallest size of such a set in G is denoted by dem(G). Denoted by G – e (resp. G\u) the subgraph of G obtained by removing the edge e from G (resp. a vertex u together with all its incident edges from G). In this paper, we first show that dem(G – e) – dem(G) ≤ 2 for any graph G and edge e ∈ E(G). Moreover, the bound is sharp. Next, we construct two graphs G and H to show that dem(G) – dem(G\u) and dem(H \ v) – dem(H) can be arbitrarily large, where u ∈ V(G) and v ∈ V(H). We also study the relation between dem(H) and dem(G), where H is a subgraph of G. In the end, we give an algorithm to judge whether the distance-edge-monitoring set still remain in the resulting graph when any edge of a graph G is deleted. [ABSTRACT FROM AUTHOR]

The smallest enclosing circle is a well-known problem. In this paper, we propose modifications to speed-up the existing Weltzl's algorithm. We perform the preprocessing to reduce as many input points as possible. The reduction step has lower computational complexity than the Weltzl's algorithm and thus speed-ups its computation. Next, we propose some changes to Weltzl's algorithm. In the end are summarized results, that show the speed-up for 10 6 input points up to 100 times compared to the original Weltzl's algorithm. Even more, the proposed algorithm is capable to process significantly larger data sets than the standard Weltzl's algorithm. [ABSTRACT FROM AUTHOR]

System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model. [ABSTRACT FROM AUTHOR]

A special class of monotone Boolean functions coming from shadow minimization theory of finite set-systems – KK-MBF functions – is considered. These functions are a descriptive model for systems of compatible groups of constraints, however, the class of all functions is unambiguously complex and it is sensible to study relatively simple subclasses of functions such as KK-MBF. Zeros of KK-MBF functions correspond to initial segments of lexicographic order on hypercube layers. This property is used to simplify the recognition. Lexicographic order applies priorities over constraints which is applicable property of practices. Query-based algorithms for KK-MBF functions are investigated in terms of their complexities. [ABSTRACT FROM AUTHOR]

Over the past decades, many methods have been proposed to solve the linear or nonlinear mixing of spectra inside the hyperspectral data. Due to a relatively low spatial resolution of hyperspectral imaging, each image pixel may contain spectra from multiple materials. In turn, hyperspectral unmixing is finding these materials and their abundances. A few main approaches to performing hyperspectral unmixing have emerged, such as nonnegative matrix factorization (NMF), linear mixture modelling (LMM), and, most recently, autoencoder networks. These methods use different approaches in finding the endmember and abundance of information from hyperspectral images. However, due to the huge variation of hyperspectral data being used, it is difficult to determine which methods perform sufficiently on which datasets and if they can generalize on any input data to solve hyperspectral unmixing problems. By trying to mitigate this problem, we propose a hyperspectral unmixing algorithm testing methodology and create a standard benchmark to test already available and newly created algorithms. A few different experiments were created, and a variety of hyperspectral datasets in this benchmark were used to compare openly available algorithms and to determine the best-performing ones. [ABSTRACT FROM AUTHOR]

This contribution presents a brief survey of clipping and intersection algorithms in E 2 and E 3 with a nearly complete list of relevant references. Some algorithms use the projective extension of the Euclidean space and vector-vector operations, which support GPU and SSE use. This survey is intended to help researchers, students, and practitioners dealing with intersection and clipping algorithms. [ABSTRACT FROM AUTHOR]

Context: Petri net slicing is a technique to reduce the size of a Petri net to ease the analysis or understanding of the original Petri net. Objective: Presenting two new Petri net slicing algorithms to isolate those places and transitions of a Petri net (the slice) that may contribute tokens to one or more places given (the slicing criterion). Method: The two algorithms proposed are formalized. The maximality of the first algorithm and the minimality of the second algorithm are formally proven. Both algorithms together with three other state-of-the-art algorithms have been implemented and integrated into a single tool so that we have been able to carry out a fair empirical evaluation. Results: Besides the two new Petri net slicing algorithms, a public, free, and open-source implementation of five algorithms is reported. The results of an empirical evaluation of the new algorithms and the slices they produce are also presented. Conclusions: The first algorithm collects all places and transitions that may contribute tokens (in any computation) to the slicing criterion, while the second algorithm collects the places and transitions needed to fire the shortest transition sequence that contributes tokens to some place in the slicing criterion. Therefore, the net computed by the first algorithm can reproduce any computation that contributes tokens to any place of interest. In contrast, the second algorithm loses this possibility, but it often produces a much more reduced subnet (which still can reproduce some computations that contribute tokens to some places of interest). The first algorithm is proven maximal, and the second one is proven minimal. [ABSTRACT FROM AUTHOR]

A sound and complete algorithm for nominal unification of higher-order expressions with a recursive let is described, and shown to run in nondeterministic polynomial time. We also explore specializations like nominal letrec-matching for expressions, for DAGs, and for garbage-free expressions and determine their complexity. We also provide a nominal unification algorithm for higher-order expressions with recursive let and atom-variables, where we show that it also runs in nondeterministic polynomial time. In addition we prove that there is a guessing strategy for nominal unification with letrec and atom-variable that is a trade-off between exponential growth and non-determinism. Nominal matching with variables representing partial letrec-environments is also shown to be in NP. [ABSTRACT FROM AUTHOR]