論文の概要: Explorability in Pushdown Automata

• arxiv url: http://arxiv.org/abs/2511.04048v1
• Date: Thu, 06 Nov 2025 04:35:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-07 20:17:53.302129
• Title: Explorability in Pushdown Automata
• Title（参考訳）: プッシュダウンオートマタの探索可能性
• Authors: Ayaan Bedi, Karoliina Lehtinen,
• Abstract要約: 本稿では,歴史決定論を一般化するプッシュダウンオートマトンにおける非決定論の尺度である探索可能性について検討する。 探索可能なPDAは、歴史決定論よりも指数関数的に簡潔であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study explorability, a measure of nondeterminism in pushdown automata, which generalises history-determinism. An automaton is k-explorable if, while reading the input, it suffices to follow k concurrent runs, built step-by-step based only on the input seen so far, to construct an accepting one, if it exists. We show that the class of explorable PDAs lies strictly between history-deterministic and fully nondeterministic PDAs in terms of both expressiveness and succinctness. In fact increasing explorability induces an infinite hierarchy: each level k defines a strictly more expressive class than level k-1, yet the entire class remains less expressive than general nondeterministic PDAs. We then introduce a parameterized notion of explorability, where the number of runs may depend on input length, and show that exponential explorability precisely captures the context-free languages. Finally, we prove that explorable PDAs can be doubly exponentially more succinct than history-deterministic ones, and that the succinctness gap between deterministic and 2-explorable PDAs is not recursively enumerable. These results position explorability as a robust and operationally meaningful measure of nondeterminism for pushdown systems.
• Abstract（参考訳）: 本稿では,歴史決定論を一般化するプッシュダウンオートマトンにおける非決定論の尺度である探索可能性について検討する。 オートマトンがk探索可能であるのは、入力を読みながら k の同時実行に従うだけで十分であり、これまで見てきた入力のみに基づいてステップバイステップで構築され、もし存在すれば受け入れ可能なものを構築するためである。 探索可能なPDAのクラスは、表現性および簡潔性の両方の観点から、歴史決定性PDAと完全に非決定性PDAの間に厳密に関係していることを示す。 実際、探索可能性の増大は無限階層を誘導する: 各レベル k はレベル k-1 よりも厳密に表現的なクラスを定義するが、クラス全体は一般の非決定論的 PDA よりも表現的でない。 次に,実行回数が入力長に依存する可能性のある探索可能性というパラメータ化概念を導入し,指数的探索可能性が文脈自由言語を正確に捉えることを示す。 最後に、探索可能なPDAは歴史決定論よりも指数関数的に簡潔であり、決定論的PDAと2-探索可能なPDAの間の簡潔さのギャップは再帰的に計算できないことを証明した。 これらの結果は、探索可能性(Explorability)を、プッシュダウンシステムに対する非決定性(nondeterminism)の堅牢かつ運用的に意味のある尺度として位置づけている。

関連論文リスト

• GSSF: Generalized Structural Sparse Function for Deep Cross-modal Metric Learning [51.677086019209554]
  ペアワイド類似性学習のためのモダリティ間の強力な関係を捕捉する汎用構造スパースを提案する。 距離メートル法は、対角線とブロック対角線の2つの形式を微妙にカプセル化する。 クロスモーダルと2つの余分なユニモーダル検索タスクの実験は、その優位性と柔軟性を検証した。
  論文  参考訳（メタデータ） (2024-10-20T03:45:50Z)
• Quality Diversity for Robot Learning: Limitations and Future Directions [6.818634856205417]
  品質多様性(QD: Quality Diversity)は、ロボットスキル学習のための高性能で多様なポリシーを発見することに成功している。 我々は、オープンな検索と一般化を容易にするために、新しいパラダイムを開発する必要があると論じている。
  論文  参考訳（メタデータ） (2024-07-09T23:29:54Z)
• From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practice [0.0]
  我々は学習されたセット辞書に焦点をあてる。 我々は、既知の専門用語を補完する新しいパラダイムを提案し、任意のSorted Set Dictionaryの学習版を作成できる。
  論文  参考訳（メタデータ） (2023-09-02T13:52:53Z)
• Algorithms for Weighted Pushdown Automata [96.29471304123844]
  重み付きプッシュダウンオートマトン(WPDA)は多くの自然言語処理タスクの中核にある。 WPDA上で直接動作する新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-13T10:21:31Z)
• Supporting Vision-Language Model Inference with Confounder-pruning Knowledge Prompt [71.77504700496004]
  視覚言語モデルは、オープンセットの視覚概念を扱うために、画像とテキストのペアを共通の空間に整列させることで事前訓練される。 事前訓練されたモデルの転送可能性を高めるため、最近の研究では、固定または学習可能なプロンプトが採用されている。 しかし、どのようにして、どのプロンプトが推論性能を改善するのかは、まだ不明である。
  論文  参考訳（メタデータ） (2022-05-23T07:51:15Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  複合イベント認識(CER)システムは、イベントのリアルタイムストリーム上のパターンを"即時"検出する能力によって、過去20年間に人気が高まっている。 このような現象が実際にCERエンジンによって検出される前に、パターンがいつ発生するかを予測する方法が不足している。 複雑なイベント予測の問題に対処しようとする形式的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-09-01T09:52:31Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。 我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
  論文  参考訳（メタデータ） (2021-04-08T17:31:34Z)

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

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