論文の概要: Right Divisibility in Erasing Semi-Thue Systems: A Minimal View of Intruder Deduction
- arxiv url: http://arxiv.org/abs/2608.03274v2
- Date: Thu, 06 Aug 2026 03:49:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-07 17:43:06.62073
- Title: Right Divisibility in Erasing Semi-Thue Systems: A Minimal View of Intruder Deduction
- Title（参考訳）: 半プロセスの消去における右の可視性:侵入者推論の最小視点
- Abstract要約: 我々は最小構造の観点から推論を研究する。
我々は、収束した同時変数リフトシステムに対して、既に推論は決定不可能であることを示す。
- 参考スコア（独自算出の注目度）: 1.1939716160985172
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The intruder deduction problem is central to symbolic security-protocol analysis: it asks whether an attacker can derive a target message from observed messages using (cryptographic) operators available to the attacker. Although convergent rewrite systems provide canonical normal forms, deduction modulo convergent theories remains undecidable in general, and existing decidable fragments are often shaped by practical cryptographic examples. In this paper, we study deduction from a minimal structural perspective. When all function symbols are unary, terms collapse to words and deduction becomes a right-divisibility problem for semi-Thue systems: given words $u$ and $v$ decide whether there exists $w$ such that $wu \equiv_S v$. We investigate this problem for several classes of semi-Thue systems and prove, to the best of our knowledge, new decidability results for convergent prefix-erasing and convergent suffix-erasing systems. We then extend this perspective to term rewriting systems whose rules erase contexts while lifting selected subterms or variables. Although these classes suggest possible decidable generalisations beyond the unary setting, we show that deduction is already undecidable for a convergent simultaneous variable-lifting system. This exposes both the potential and the limits of extending the right-divisibility results to richer equational theories.
- Abstract（参考訳）: 攻撃者は、攻撃者に利用可能な(暗号化)演算子を使用して、観測されたメッセージからターゲットメッセージを導出できるかどうかを問う。
収束書き直し系は標準正規形式を提供するが、推論モジュラー収束理論は一般には決定不可能であり、既存の決定可能な断片は実践的な暗号的な例によってしばしば形作られる。
本稿では,最小構造の観点からの推論について考察する。
すべての関数記号が一意的であるとき、項が単語に崩壊し、導出が半列系において正しい可分性問題となる: 与えられた単語$u$と$v$は、$w$が存在して$wu \equiv_S v$であるかどうかを決定する。
そこで本研究では, 半列系のいくつかのクラスにおいてこの問題を考察し, 最善を尽くすために, 収束接頭辞・接尾辞・接尾辞・接尾辞・接尾辞・接尾辞・接尾辞・接尾辞・接尾辞・接尾辞・接尾辞・接尾辞・接尾辞の新たな決定可能性について検証する。
次に、この視点を、選択したサブターまたは変数を持ち上げながら、ルールがコンテキストを消去する項書き換えシステムに拡張する。
これらのクラスは、一意的な設定を超えて決定可能な一般化が可能であることを示唆するが、導出は、収束した同時変数リフトシステムに対して既に決定不可能であることを示す。
これは、よりリッチな方程式理論に右分割結果を拡張する可能性と限界の両方を露呈する。
関連論文リスト
- What Syntax Cannot See: The Dynamic Syntactic Invariance Principle and Several Instances of the Same Hidden Assumption, and a Contradiction [0.0]
本稿では, 一つの手法を開発し, 受理結果を無声で仮定し, 変数とし, 一度落として何に従うかを証明する。
共通点のないドメイン間で動作し続けることを示すものだ。
論文 参考訳（メタデータ） (2026-08-02T03:10:44Z) - A cubical formalisation of topos causal models: intervention, sheaf gluing, and the intuitionistic do-calculus [5.076419064097734]
1-toposコアの最初のマシンチェックをCuical Agdaで行います。
我々はすべてのトポロジーの下で介入とパールの規則が安定していることを示す。
我々は、そのプログラムが考慮しない現象、すなわち、マシンチェックされた文脈性障害を加える。
論文 参考訳（メタデータ） (2026-07-17T05:05:31Z) - The Need for an External Observer Formalizing the Sufficiency Gap: A Mathematical Extension of Mixture Identifiability and Contextual Grounding in Sequence Models [0.0]
我々は、決定論的テキスト構造と、保存されていない潜在状態によって支配される1つのランダム構造を持つ2元混合登録プロセスを構築した。
結果として生じるエントロピー差は通常の最適化誤差ではない。
補正信号は、その忠実度が誤解を招く状態に割り当てられたテキストのみの後方重みを超えると、テキスト履歴によって引き起こされる後続のオッズを正確に反転させる。
論文 参考訳（メタデータ） (2026-05-26T08:53:11Z) - Learning Visual-Semantic Subspace Representations [49.17165360280794]
我々は,自己教師型学習に有効な情報理論の原理を基礎として,核ノルムに基づく損失関数を導入する。
この損失の理論的特徴として、クラス性の促進に加えて、部分空間格子内のデータのスペクトル幾何学を符号化していることを示す。
論文 参考訳（メタデータ） (2024-05-25T12:51:38Z) - Bisimulation Learning [55.859538562698496]
我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。
提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
論文 参考訳（メタデータ） (2024-05-24T17:11:27Z) - A Hybrid System for Systematic Generalization in Simple Arithmetic
Problems [70.91780996370326]
本稿では,記号列に対する合成的および体系的推論を必要とする算術的問題を解くことができるハイブリッドシステムを提案する。
提案システムは,最も単純なケースを含むサブセットでのみ訓練された場合においても,ネストした数式を正確に解くことができることを示す。
論文 参考訳（メタデータ） (2023-06-29T18:35:41Z) - A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
論文 参考訳（メタデータ） (2022-10-27T17:59:09Z) - The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for
Two-Dimensional Systems [62.997667081978825]
開量子系は、FGKLS(Franke-Gorini-Kossakowski-Lindblad-Sudarshan)方程式に従うことができる。
我々はヒルベルト空間次元が 2$ である場合を徹底的に研究する。
論文 参考訳（メタデータ） (2022-04-16T07:03:54Z) - Scattering data and bound states of a squeezed double-layer structure [77.34726150561087]
2つの平行な均質層からなる構造は、その幅が$l_j$と$l_j$であり、それらの間の距離が$r$を同時に0に縮めるように、極限において研究される。
非自明な有界状態の存在は、ディラックのデルタ関数の微分の形で圧縮ポテンシャルの特別な例を含む、スクイーズ極限で証明される。
有限系の有限個の有界状態から、一個の有界状態が圧縮された系で生き残るシナリオを詳述する。
論文 参考訳（メタデータ） (2020-11-23T14:40:27Z) - Adversarial Classification: Necessary conditions and geometric flows [0.7614628596146599]
本研究では,ある逆数分類法を用いて,ある距離から最大$varepsilon$までデータ入力を不正に入力する逆数分類法について検討する。
我々は、分類境界の変化を$varepsilon$の変分として追跡するために使用できる幾何学的進化方程式を導出する。
論文 参考訳（メタデータ） (2020-11-21T14:14:12Z) - Sub-bosonic (deformed) ladder operators [62.997667081978825]
ファジィネスという厳密な概念から派生した変形生成および消滅作用素のクラスを提示する。
これにより変形し、ボゾン準可換関係は、修正された退化エネルギーとフォック状態を持つ単純な代数構造を誘導する。
さらに、量子論において導入された形式論がもたらす可能性について、例えば、自由準ボソンの分散関係における線型性からの偏差について検討する。
論文 参考訳（メタデータ） (2020-09-10T20:53:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。