論文の概要: Pushing the Limits: Concurrency Detection in Acyclic, Live, and 1-Safe
Free-Choice Nets in $O\big((P + T)^2\big)$
- arxiv url: http://arxiv.org/abs/2401.16097v1
- Date: Mon, 29 Jan 2024 12:11:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-30 15:04:34.253740
- Title: Pushing the Limits: Concurrency Detection in Acyclic, Live, and 1-Safe
Free-Choice Nets in $O\big((P + T)^2\big)$
- Title（参考訳）: 限界を押し上げる:$O\big((P + T)^2\big)$における非環状, ライブ, 1-セーフフリーチョイスネットにおける並行検出
- Authors: Thomas M. Prinz, Julien Klaus, Nick R.T.P. van Beest
- Abstract要約: どの場所とトランジションを並列に実行できるかを知ることは、ネットを理解するのに役立つ。
本稿では、検出アルゴリズムのパレットを、安全でライブな自由選択ネットのための Concurrent Paths (CP) アルゴリズムで補完する。
- 参考スコア（独自算出の注目度）: 0.9208007322096533
- 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 nets (where
$P$ and $T$ are the numbers of places and transitions) and in
$O\big(P(P+T)^2\big)$ for live 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. Furthermore, both algorithms
cannot be parallelized without additional effort. This paper complements the
palette of concurrency detection algorithms with the Concurrent Paths (CP)
algorithm for safe, live, free-choice nets. The algorithm allows
parallelization and has a worst-case computational complexity of
$O\big((P+T)^2\big)$ for acyclic nets and of $O\big(P^3+PT^2\big)$ 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（参考訳）: 並列性は複雑なシステムの振る舞いを記述しシミュレートする(petri)ネットの重要な側面である。
どの場所と遷移が並列に実行されるかを知ることは、ネットを理解し、因果性、排他性など他の特性の分析技術や計算を可能にする。
並列検出に基づくすべての手法は、この検出手法の効率に依存する。
Kovalyov と Esparza は、ライブネットでは$O\big((P+T)TP^2\big)$、ライブ無料ネットでは$O\big(P(P+T)^2\big)$で計算するアルゴリズムを開発した。
これらのアルゴリズムは計算の複雑さがかなり高いが、多くの並列ノードが長い計算時間に繋がる可能性がある。
さらに、両方のアルゴリズムは追加の労力なしで並列化できない。
本稿では, 並列性検出アルゴリズムのパレットを, 安全, ライブ, フリーチョイスネットのための並列パス (cp) アルゴリズムで補完する。
このアルゴリズムは並列化が可能であり、非巡回ネットは$O\big((P+T)^2\big)$、サイクリックネットは$O\big(P^3+PT^2\big)$である。
循環網の計算複雑性は改善されていないが、CPの利点、特に並列関係において多くのノードを含む場合の利点が評価されている。
関連論文リスト
- Scalable network reconstruction in subquadratic time [0.0]
本稿では,幅広い再構成問題に適用可能な汎用アルゴリズムを提案する。
我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
論文 参考訳（メタデータ） (2024-01-02T19:00:13Z) - Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。
このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。
シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文 参考訳（メタデータ） (2023-05-25T22:27:42Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Can stable and accurate neural networks be computed? -- On the barriers
of deep learning and Smale's 18th problem [0.5801044612920815]
ディープラーニング(DL)は前例のない成功を収め、現在は全力で科学計算に参入している。
DLは、不安定なニューラルネットワーク(NN)の存在をしばしば保証する普遍的な近似特性にもかかわらず、普遍的な現象に苦しむ
このようなNNを訓練(あるいは計算)できるアルゴリズムが,ランダム化されてさえ存在しないことを示す。
我々は、Fast Iterative Restarted NETworks (FIRENETs)を紹介し、それを証明し、数値的に検証する。
論文 参考訳（メタデータ） (2021-01-20T19:04:17Z) - 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) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳（メタデータ） (2020-06-15T21:36:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。