論文の概要: Decidability of cutpoint isolation for probabilistic finite automata on
letter-bounded inputs
- arxiv url: http://arxiv.org/abs/2002.07660v2
- Date: Thu, 14 May 2020 09:58:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 20:28:45.104679
- Title: Decidability of cutpoint isolation for probabilistic finite automata on
letter-bounded inputs
- Title（参考訳）: 文字境界入力に対する確率的有限オートマトンに対するカットポイント分離の決定可能性
- Authors: Paul C. Bell and Pavel Semukhin
- Abstract要約: 確率的有限オートマタ(PFA)においてカットポイント分離問題が決定可能であるという驚くべき結果を示す。
PFAが指数的不明瞭である場合でも保持するカットポイント分離問題を解決するための構成的非決定論的アルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 0.1269104766024433
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show the surprising result that the cutpoint isolation problem is
decidable for Probabilistic Finite Automata (PFA) where input words are taken
from a letter-bounded context-free language. A context-free language
$\mathcal{L}$ is letter-bounded when $\mathcal{L} \subseteq a_1^*a_2^* \cdots
a_\ell^*$ for some finite $\ell > 0$ where each letter is distinct. A cutpoint
is isolated when it cannot be approached arbitrarily closely. The decidability
of this problem is in marked contrast to the situation for the (strict)
emptiness problem for PFA which is undecidable under the even more severe
restrictions of PFA with polynomial ambiguity, commutative matrices and input
over a letter-bounded language as well as to the injectivity problem which is
undecidable for PFA over letter-bounded languages. We provide a constructive
nondeterministic algorithm to solve the cutpoint isolation problem, which holds
even when the PFA is exponentially ambiguous. We also show that the problem is
at least NP-hard and use our decision procedure to solve several related
problems.
- Abstract（参考訳）: 文字境界のない文脈自由言語から入力語を取り出す確率的有限オートマタ(PFA)に対して,カットポイント分離問題が決定可能であるという驚くべき結果を示す。
文脈自由言語 $\mathcal{L}$ は、ある有限$\ell > 0$ に対して $\mathcal{L} \subseteq a_1^*a_2^* \cdots a_\ell^*$ のとき、文字境界となる。
カットポイントは、任意に接近できないときに分離される。
この問題の決定性は、多項式あいまいさ、可換行列および文字有界言語への入力によるPFAのより厳しい制限の下では決定不可能なPFAの(限定的な)空白問題や、文字有界言語上のPFAでは決定不可能なインジェクティビティ問題と対照的である。
PFAが指数的不明瞭である場合でも、切断点分離問題を解決するための構成的非決定論的アルゴリズムを提供する。
また、この問題は少なくともNPハードであり、決定手順を用いていくつかの問題を解くことも示している。
関連論文リスト
- Markov Constraint as Large Language Model Surrogate [49.86129209397701]
NgramMarkovは制約プログラミング(CP)におけるテキスト生成に特化している
これは文のn-グラムの確率の積を制限する。
5グラムではなく4グラムで現実の問題が初めて解決された。
論文 参考訳（メタデータ） (2024-06-11T16:09:53Z) - Box Facets and Cut Facets of Lifted Multicut Polytopes [2.531156266686649]
昇降型マルチカット問題の線形プログラム定式化について検討する。
2進線形プログラムのカット不等式がファセットを定義するかどうかを決定することはNPハードであることを示す。
論文 参考訳（メタデータ） (2024-02-26T18:37:16Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Directed Regular and Context-Free Languages [0.6906005491572399]
言語$L$は、$L$のすべての単語が$L$の共通の(散在した)スーパーワードを持っている場合、emphdirectedされる。
文脈自由言語では、有向性問題はcoNEXP完全であることが知られている。
文脈自由言語では、有向性問題はPSPACE完全であることを示す。
論文 参考訳（メタデータ） (2024-01-13T16:13:45Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Rewindable Quantum Computation and Its Equivalence to Cloning and
Adaptive Postselection [0.0]
sf PostBQP$の任意の問題は、確率が1に近いポストセレクションのみによって解決できることを示す。
また,1つの逆風演算子が量子計算に難解なタスクを達成するのに十分であることを示す。
論文 参考訳（メタデータ） (2022-06-11T06:19:24Z) - Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。
この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
論文 参考訳（メタデータ） (2022-05-16T15:47:41Z) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文 参考訳（メタデータ） (2022-03-24T08:14:12Z) - Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method [54.93433440034386]
実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
論文 参考訳（メタデータ） (2020-10-05T08:16:56Z) - The Power of a Single Qubit: Two-way Quantum Finite Automata and the
Word Problem [0.0]
量子および古典状態を持つ2方向有限オートマトン(2QCFA)は、量子部分が非常に限定された量子計算のモデルである。
2QCFA は期待時間で $L_eq=am bm :m mathbbN$ を認識でき、a,b*:w CFA CFA は期待指数時間で parindrome$ を認識できることを示す。
論文 参考訳（メタデータ） (2020-03-22T12:46:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。