Fugu-MT 論文翻訳(概要): Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete

論文の概要: Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete

arxiv url: http://arxiv.org/abs/2508.09784v1
Date: Wed, 13 Aug 2025 13:10:16 GMT
ステータス: 翻訳完了
システム内更新日: 2025-08-14 20:42:00.894678
Title: Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete
Title（参考訳）: 正規表現に関する知識の推論は2EXPTIME完全である
Authors: Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber,
Abstract要約: 公開観測論理 (Public Observation Logic, POL) は、公開観測に基づいて更新される知識を推論するための、公開発表論理の変種である。本研究では,$POL$の満足度問題は2EXPTIME完全であることを証明した。
参考スコア（独自算出の注目度）: 10.556561707281846
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Logics for reasoning about knowledge and actions have seen many applications in various domains of multi-agent systems, including epistemic planning. Change of knowledge based on observations about the surroundings forms a key aspect in such planning scenarios. Public Observation Logic (POL) is a variant of public announcement logic for reasoning about knowledge that gets updated based on public observations. Each state in an epistemic (Kripke) model is equipped with a set of expected observations. These states evolve as the expectations get matched with the actual observations. In this work, we prove that the satisfiability problem of $\POL$ is 2EXPTIME-complete.
Abstract（参考訳）: 知識と行動に関する推論の論理学は、疫学計画を含む多エージェントシステムの様々な領域で多くの応用を見てきた。周囲の観察に基づく知識の変化は、このような計画シナリオにおいて重要な側面を形成する。公開観測論理 (Public Observation Logic, POL) は、公開観測に基づいて更新される知識を推論するための、公開発表論理の変種である。てんかん(Kripke)モデルの各状態には、期待される観測のセットが備わっている。これらの状態は、期待が実際の観測と一致するように進化する。本研究では,$\POL$の満足度問題は2EXPTIME完全であることを証明した。

関連論文リスト

A Semantic Approach to Decidability in Epistemic Planning (Extended Version) [72.77805489645604]
我々は決定可能性を達成するために新しい意味論的アプローチを用いる。具体的には、知識の論理S5$_n$と(知識)可換性と呼ばれる相互作用公理を拡大する。我々は,本フレームワークが,独立した知識である共通知識の有限的非固定点的特徴を認めていることを証明した。
論文参考訳（メタデータ） (2023-07-28T11:26:26Z)
Logic meets Wigner's Friend (and their Friends) [49.1574468325115]
我々は、Wignerのフレンドの思考体験と、そのより最近の変種と拡張について、新しい見返りをする。本稿では,いくつかの疑問に焦点をあてて,文献で提案される様々な解決策について論じる。
論文参考訳（メタデータ） (2023-07-04T13:31:56Z)
On simple expectations and observations of intelligent agents: A complexity study [3.077802365568915]
POL(Public Observation logic)は、様々な現実の状況におけるエージェントの期待とエージェントの観察に関する理由である。本研究では, POLの種々のフラグメントの満足度問題に対する計算複雑性について検討する。その過程では、これらのフラグメントがよく研究されているパブリックな発表ロジックと必然的に結びついている点を強調します。
論文参考訳（メタデータ） (2023-06-05T10:53:27Z)
Generic Temporal Reasoning with Differential Analysis and Explanation [61.96034987217583]
時間差分解析でギャップを埋めるTODAYという新しいタスクを導入する。 TODAYは、システムがインクリメンタルな変化の効果を正しく理解できるかどうかを評価する。共同学習においてTODAYの指導スタイルと説明アノテーションが有効であることを示す。
論文参考訳（メタデータ） (2022-12-20T17:40:03Z)
A calculus for epistemic interactions [0.5156484100374059]
E-calculusはエージェントの環境との相互作用をモデル化するための概念フレームワークである。本稿では,エージェントの環境との相互作用をモデル化するための概念フレームワークであるe-calculusを提案する。 e-計算の挙動論は2つの異なる視点で展開される。
論文参考訳（メタデータ） (2022-06-29T09:54:58Z)
On verifying expectations and observations of intelligent agents [3.077802365568915]
パブリック・オブザーバ・ロジック (Public Observation logic, POL) は、エージェントの期待とエージェントの観察を推論するダイナミック・エピステミック・ロジックの変種である。本研究では,POLのモデルチェック問題の計算複雑性について検討し,そのPSPACE完全性を証明する。本研究では,POLモデル検査の適用性を実証し,対話システムの異なる特性と特徴を,システムの異なる期待と(マッチング)観察に対して検証する。
論文参考訳（メタデータ） (2022-05-02T10:09:49Z)
Visual Abductive Reasoning [85.17040703205608]
帰納的推論は、部分的な観察の可能な限りの可能な説明を求める。本稿では,日常的な視覚的状況下でのマシンインテリジェンスの帰納的推論能力を調べるために,新たなタスクとデータセットであるVisual Abductive Reasoning(VAR)を提案する。
論文参考訳（メタデータ） (2022-03-26T10:17:03Z)
Thirty years of Epistemic Specifications [8.339560855135575]
我々は、主観的リテラルと呼ばれるモーダル構造を持つ安定モデルセマンティクスの下で、解法論理プログラムを拡張した。主観的リテラルを用いることで、プログラムのすべての安定モデルで正規リテラルが真かどうかを確認することができる。形式的な意味論によって言語の基礎となる直観を捉えようとするいくつかの試みが与えられた。
論文参考訳（メタデータ） (2021-08-17T15:03:10Z)
Generalized Inverse Planning: Learning Lifted non-Markovian Utility for Generalizable Task Representation [83.55414555337154]
本研究では,人間の実演からこのような有用性を学ぶことを研究する。本稿では,本領域におけるユーティリティ学習のための新しい探索手法である一般化逆計画を提案する。計算フレームワークである最大エントロピー逆計画(MEIP)について概説し、非マルコフ的効用と関連する概念を生成的に学習する。
論文参考訳（メタデータ） (2020-11-12T21:06:26Z)
Causal Discovery in Physical Systems from Videos [123.79211190669821]
因果発見は人間の認知の中心にある。本研究では,ビデオの因果発見の課題を,地層構造を監督せずにエンドツーエンドで検討する。
論文参考訳（メタデータ） (2020-07-01T17:29:57Z)

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