Pushing the Limits: Concurrency Detection in Acyclic Sound Free-Choice Workflow Nets in $O(P^2 + T^2)$

• URL: http://arxiv.org/abs/2401.16097v2
• Date: Thu, 21 Mar 2024 13:29:03 GMT
• Title: Pushing the Limits: Concurrency Detection in Acyclic Sound Free-Choice Workflow Nets in $O(P^2 + T^2)$
• Authors: Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest,
• Abstract summary: Knowing which places and transitions could be executed in parallel helps to understand computation nets. Kovalyov and Esparza have developed algorithms that compute all concurrent places in $Obig((P+T)TP2big)$ for live and bounded nets. This paper complements the palette of detection algorithms with the Concurrent Paths (CP) algorithm for sound free-choice workflow nets.
• Score: 0.8192907805418583
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Concurrency is an important aspect of Petri nets to describe and simulate the behavior of complex systems. Knowing which places and transitions could be executed in parallel helps to understand nets and enables analysis techniques and the computation of other properties, such as causality, exclusivity, etc.. All techniques based on concurrency detection depend on the efficiency of this detection methodology. Kovalyov and Esparza have developed algorithms that compute all concurrent places in $O\big((P+T)TP^2\big)$ for live and bounded nets (where $P$ and $T$ are the numbers of places and transitions) and in $O\big(P(P+T)^2\big)$ for live and bounded free-choice nets. Although these algorithms have a reasonably good computational complexity, large numbers of concurrent pairs of nodes may still lead to long computation times. This paper complements the palette of concurrency detection algorithms with the Concurrent Paths (CP) algorithm for sound free-choice workflow nets. The algorithm allows parallelization and has a worst-case computational complexity of $O(P^2 + T^2)$ for acyclic nets and of $O(P^3 + PT^2)$ for cyclic nets. Although the computational complexity of cyclic nets has not improved, the evaluation shows the benefits of CP, especially, if the net contains many nodes in concurrency relation.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Scalable network reconstruction in subquadratic time [0.0]
  We present a general algorithm applicable to a broad range of reconstruction problems that significantly outperforms this quadratic baseline. Our algorithm relies on a second neighbor search that produces the best edge candidates with high probability. We show that our algorithm achieves a performance that is many orders of magnitude faster than the quadratic baseline.
  arXiv  Detail & Related papers  (2024-01-02T19:00:13Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
  We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability. The algorithms achieve a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. An existing framework for using distributed version of Grover's search algorithm to accelerate triangle finding lies at the core of the speedup.
  arXiv  Detail & Related papers  (2023-04-06T02:18:52Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm. Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• A Quantum Algorithm for Network Reliability [0.033842793760651545]
  We present an explicit, circuit-level implementation of a quantum algorithm that computes $R$. Our algorithm requires $O(EV/epsilon)$ gate operations and $O(E)$bits, where $V$ and $E$ are the number nodes and edges.
  arXiv  Detail & Related papers  (2022-03-19T00:26:52Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  We show that a given suboptimality $epsilon0$ is achieved master/workers networks in $Omegabig. We then propose algorithms matching the lower bounds either types of networks (up to log-overs) We assess effectiveness of the proposed algorithms on a robust logistic regression problem.
  arXiv  Detail & Related papers  (2021-07-22T14:25:16Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  We show that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate. We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(log n)$ competitive.
  arXiv  Detail & Related papers  (2020-12-17T04:56:51Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.