論文の概要: Reachability in symmetric VASS

• arxiv url: http://arxiv.org/abs/2506.23578v1
• Date: Mon, 30 Jun 2025 07:33:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-01 21:27:53.95855
• Title: Reachability in symmetric VASS
• Title（参考訳）: 対称VASSの到達性
• Authors: Łukasz Kamiński, Sławomir Lasota,
• Abstract要約: 状態を持つ対称ベクトル加算系の到達可能性問題について検討する。 極端の場合、自明な群は一般のVASSをもたらす。 別の極端の場合、対称群では、到達性問題はPSPACEで解決できることが示される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the reachability problem in symmetric vector addition systems with states (VASS), where transitions are invariant under a group of permutations of coordinates. One extremal case, the trivial groups, yields general VASS. In another extremal case, the symmetric groups, we show that the reachability problem can be solved in PSPACE, regardless of the dimension of input VASS (to be contrasted with Ackermannian complexity in general VASS). We also consider other groups, in particular alternating and cyclic ones. Furthermore, motivated by the open status of the reachability problem in data VASS, we estimate the gain in complexity when the group arises as a combination of the trivial and symmetric groups.
• Abstract（参考訳）: 状態 (VASS) を持つ対称ベクトル加算系において、遷移が座標の置換群の下で不変であるような到達可能性問題について検討する。 極端の場合、自明な群は一般のVASSをもたらす。 別の極端の場合、対称群では、入力 VASS の次元に関係なく、到達性問題は PSPACE で解くことができる(一般に VASS のアッカーマン複雑性と対比する)。 また、他の群、特に交互群や巡回群についても検討する。 さらに,データVASSにおける到達可能性問題のオープンな状態から,群が自明な群と対称な群の組合せとして現れるときの複雑性の増大を推定する。

関連論文リスト

• A3S: A General Active Clustering Method with Pairwise Constraints [66.74627463101837]
  A3Sは、適応クラスタリングアルゴリズムによって得られる初期クラスタ結果に対して、戦略的にアクティブクラスタリングを調整する。 さまざまな実世界のデータセットにわたる広範な実験において、A3Sは、人間のクエリを著しく少なくして、望ましい結果を達成する。
  論文  参考訳（メタデータ） (2024-07-14T13:37:03Z)
• Classifying symmetric and symmetry-broken spin chain phases with anomalous group actions [0.0]
  局所分解可能群作用の下で不変な量子スピン鎖の分類問題を考察する。 我々は、自然に一次元対称性に保護された位相位相をカバーする分類の不変性を導出する。
  論文  参考訳（メタデータ） (2024-03-27T13:54:45Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Sample Complexity of Probability Divergences under Group Symmetry [13.084804346845816]
  群不変分布の変分分散推定におけるサンプル複雑性の改善を厳密に定量化する。 ワッサーシュタイン1計量とリプシッツ規則化された$alpha$-divergencesの場合、標本の複雑さの減少は群が有限であれば群のサイズに比例する。
  論文  参考訳（メタデータ） (2023-02-03T18:50:15Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Constraints on Maximal Entanglement Under Groups of Permutations [73.21730086814223]
  絡み合いの集合は本質的に等しく、群作用の下で同じ軌道上にある。 物理対称性群の正規化子および正規化部分群を利用することにより、これらの絡み合いの最大値に対する新しい一般化された関係を導入する。
  論文  参考訳（メタデータ） (2020-11-30T02:21:22Z)
• Entanglement marginal problems [0.0]
  絡み合いの限界問題は、多くの還元密度行列が全体分離可能な量子状態と互換性があるかどうかを決定することである。 完全分離可能な拡張を許容する量子状態境界の集合の半定値プログラミング緩和の階層性を提案する。 我々の結果は、1次元の翻訳不変系や余剰対称性を持つ高次元など無限のシステムにまで拡張される。
  論文  参考訳（メタデータ） (2020-06-16T10:48:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。