論文の概要: Pushing the Limits: Concurrency Detection in Acyclic Sound Free-Choice Workflow Nets in $O(P^2 + T^2)$
- arxiv url: http://arxiv.org/abs/2401.16097v2
- Date: Thu, 21 Mar 2024 13:29:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-22 19:17:37.200900
- Title: Pushing the Limits: Concurrency Detection in Acyclic Sound Free-Choice Workflow Nets in $O(P^2 + T^2)$
- Title（参考訳）: 限界を押し上げる:$O(P^2 + T^2)$の非循環音フリーコースワークフローネットにおける並行検出
- Authors: Thomas M. Prinz, Julien Klaus, Nick R. T. P. van Beest,
- Abstract要約: どの場所とトランジションを並列に実行できるかを知ることは、計算ネットを理解するのに役立つ。
Kovalyov と Esparza は、Obig((P+T)TP2big)$ のすべての並列な場所をライブおよび有界ネットで計算するアルゴリズムを開発した。
本稿では,検出アルゴリズムのパレットとコンカレントパス(CP)アルゴリズムを補完する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 並行性は、複雑なシステムの振る舞いを記述し、シミュレートするペトリネットの重要な側面である。
どの場所と遷移が並列に実行されるかを知ることは、ネットを理解し、因果性、排他性など他の特性の分析技術や計算を可能にする。
並列検出に基づくすべての手法は、この検出手法の効率に依存する。
Kovalyov と Esparza は、O\big((P+T)TP^2\big)$ と有界ネット(ここでは$P$ と $T$ は場所と遷移の数)と $O\big(P(P+T)^2\big)$ と有界自由選択ネット(英語版)$ を同時に計算するアルゴリズムを開発した。
これらのアルゴリズムは計算の複雑さがかなり高いが、多くの並列ノードが長い計算時間に繋がる可能性がある。
本稿では,コンカレント検出アルゴリズムのパレットと,音声自由選択ワークフローネットのためのコンカレントパス(CP)アルゴリズムを補完する。
このアルゴリズムは並列化が可能であり、非巡回ネットは$O(P^2 + T^2)$、巡回ネットは$O(P^3 + PT^2)$である。
循環網の計算複雑性は改善されていないが、CPの利点、特に並列関係において多くのノードを含む場合の利点が評価されている。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Scalable network reconstruction in subquadratic time [0.0]
本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。
我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
論文 参考訳（メタデータ） (2024-01-02T19:00:13Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - A Quantum Algorithm for Network Reliability [0.033842793760651545]
本稿では、R$を演算する量子アルゴリズムの回路レベルを明示的に実装する。
我々のアルゴリズムでは、$O(EV/epsilon)$ gate 演算と$O(E)$bitsが必要です。
論文 参考訳（メタデータ） (2022-03-19T00:26:52Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Metrical Task Systems with Online Machine Learned Advice [0.0]
機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。
我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
論文 参考訳（メタデータ） (2020-12-17T04:56:51Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。