論文の概要: On the Size Complexity and Decidability of First-Order Progression
- arxiv url: http://arxiv.org/abs/2605.12691v1
- Date: Tue, 12 May 2026 19:40:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-14 23:30:27.651168
- Title: On the Size Complexity and Decidability of First-Order Progression
- Title（参考訳）: 第一次進行の複雑さと決定可能性について
- Authors: Jens Classen, Daxin Liu,
- Abstract要約: 局所効果、正規作用、非循環作用の3つのクラスは、一階の進行を認めている。
合理的な仮定の下では、これらのアクションクラスに対する一階述語進行は、のみ増大することを示す。
- 参考スコア（独自算出の注目度）: 2.62121275102348
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Progression, the task of updating a knowledge base to reflect action effects, generally requires second-order logic. Identifying first-order special cases, by restricting either the knowledge base or action effects, has long been a central topic in reasoning about actions. It is known that local-effect, normal, and acyclic actions, three increasingly expressive classes, admit first-order progression. However, a systematic analysis of the size of such progressions, crucial for practical applications, has been missing. In this paper, using the framework of Situation Calculus, we show that under reasonable assumptions, first-order progression for these action classes grows only polynomially. Moreover, we show that when the KB belongs to decidable fragments such as two-variable first-order logic or universal theories with constants, the progression remains within the same fragment, ensuring decidability and practical applicability.
- Abstract（参考訳）: 行動効果を反映する知識ベースを更新するタスクである進歩は、一般的に二階述語論理を必要とする。
知識ベースと行動効果のどちらかを制限することで、一階特別事例の特定は、長年にわたり、行動の推論において中心的な話題となっている。
局所効果、正規作用、非循環作用の3つのクラスは、一階の進行を認めることが知られている。
しかし、実際的な応用に欠かせない、そのような進歩の規模を体系的に分析することができない。
本稿では、状況計算の枠組みを用いて、合理的な仮定の下では、これらのアクションクラスに対する一階述語進行は多項式的にのみ増加することを示す。
さらに、KB が二変数一階述語論理や定数の普遍理論のような決定可能な断片に属する場合、その進行は同じ断片の中に留まり、決定可能性と実用性を保証する。
関連論文リスト
- Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling [60.63703438729223]
異なるアーキテクチャとトレーニング手法がモデル多段階推論能力にどのように影響するかを示す。
我々は,逐次計算においてモデル深度の増加が重要な役割を担っていることを確認した。
論文 参考訳（メタデータ） (2025-08-22T18:57:08Z) - Saving for the future: Enhancing generalization via partial logic regularization [21.8007498113196]
視覚分類タスクにおいて、一般化は依然として重要な課題である。
近年のアプローチでは、一般化を強化するために論理ベースの正則化が採用されているが、完全に定義された論理式の必要性に縛られている。
本稿では、未定義論理式に対してモデルが空間を予約できるような、新しい部分論理正規化項であるPL-Regを紹介する。
論文 参考訳（メタデータ） (2025-08-21T07:27:33Z) - Order Doesn't Matter, But Reasoning Does: Training LLMs with Order-Centric Augmentation [57.570754504160305]
本稿では,論理的推論における可換性に基づく順序中心のデータ拡張フレームワークを提案する。
秩序中心の拡張を利用することで、モデルはより柔軟で一般化された推論プロセスを開発することができる。
論文 参考訳（メタデータ） (2025-02-27T09:25:50Z) - A Strategy for Implementing description Temporal Dynamic Algorithms in
Dynamic Knowledge Graphs by SPIN [6.176867277585226]
本研究では,記述論理(DL)の拡張,時間的形式主義,行動形式主義などの関連する論理構造について検討した。
アクションの表現と推論のために、私たちはアクションをDL(Dynamic-ALCとその拡張など)に埋め込んだ。
本稿では,アクションプロジェクション,計画,満足度,一貫性,実現可能性,実行性をチェックするための用語可能なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-15T18:43:48Z) - Inverse Decision Modeling: Learning Interpretable Representations of
Behavior [72.80902932543474]
我々は,逆決定モデルに関する表現的,統一的な視点を開拓する。
これを逆問題(記述モデルとして)の形式化に用います。
この構造が(有界な)有理性の学習(解釈可能な)表現を可能にする方法について説明する。
論文 参考訳（メタデータ） (2023-10-28T05:05:01Z) - Regularization-Based Methods for Ordinal Quantification [49.606912965922504]
順序の場合、すなわち n>2 クラスの集合上で全順序が定義される場合について研究する。
本稿では,従来のアルゴリズムよりも優れた正規化OQアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-13T16:04:06Z) - A Semantic Approach to Decidability in Epistemic Planning (Extended
Version) [72.77805489645604]
我々は決定可能性を達成するために新しい意味論的アプローチを用いる。
具体的には、知識の論理S5$_n$と(知識)可換性と呼ばれる相互作用公理を拡大する。
我々は,本フレームワークが,独立した知識である共通知識の有限的非固定点的特徴を認めていることを証明した。
論文 参考訳（メタデータ） (2023-07-28T11:26:26Z) - Generalized Reinforcement Learning: Experience Particles, Action
Operator, Reinforcement Field, Memory Association, and Decision Concepts [2.398608007786179]
本稿では,ベイズ風の一般強化学習フレームワークを提案する。
まず,不確実性や流動挙動に対処するためのパラメトリック・アクション・モデルを構築した。
次に,学習者の作業記憶に保持される「偏極化経験粒子」によって確立された物理に着想を得た構成体として,強化場の概念を導入する。
論文 参考訳（メタデータ） (2022-08-09T15:05:15Z) - Characterizing the Action-Generalization Gap in Deep Q-Learning [17.377157455292814]
一般化により、エージェントは過去の経験から学んだ知識を新しいタスクで利用できる。
実験により、Deep Q-Networks (DQN) は依然として控えめな行動一般化を達成可能であることが示された。
論文 参考訳（メタデータ） (2022-05-11T16:00:46Z) - Nested Counterfactual Identification from Arbitrary Surrogate
Experiments [95.48089725859298]
観測と実験の任意の組み合わせからネスト反事実の同定について検討した。
具体的には、任意のネストされた反事実を非ネストされたものへ写像できる反ファクト的非ネスト定理(英語版)(CUT)を証明する。
論文 参考訳（メタデータ） (2021-07-07T12:51:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。