Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs

• URL: http://arxiv.org/abs/2002.07660v2
• Date: Thu, 14 May 2020 09:58:42 GMT
• Title: Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs
• Authors: Paul C. Bell and Pavel Semukhin
• Abstract summary: We show the surprising result that the cutpoint isolation problem is decidable for Probabilistic Finite Automata (PFA) We provide a constructive nondeterministic algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentially ambiguous.
• Score: 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.

Related papers

• Markov Constraint as Large Language Model Surrogate [49.86129209397701]
  NgramMarkov is dedicated to text generation in constraint programming (CP) It limits the product of the probabilities of the n-gram of a sentence. A real-world problem has been solved for the first time using 4-grams instead of 5-grams.
  arXiv  Detail & Related papers  (2024-06-11T16:09:53Z)
• Box Facets and Cut Facets of Lifted Multicut Polytopes [2.531156266686649]
  We study a binary linear program formulation of the lifted multicut problem. We show that deciding whether a cut inequality of the binary linear program defines a facet is NP-hard.
  arXiv  Detail & Related papers  (2024-02-26T18:37:16Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
  arXiv  Detail & Related papers  (2024-01-17T09:23:25Z)
• Directed Regular and Context-Free Languages [0.6906005491572399]
  A language $L$ is emphdirected if every pair of words in $L$ have a common (scattered) superword in $L$. For context-free languages, the directedness problem is known to be coNEXP-complete. We show that for context-free languages, the directedness problem is PSPACE-complete.
  arXiv  Detail & Related papers  (2024-01-13T16:13:45Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection [0.0]
  We show that any problem in $sf PostBQP$ can be solved with only postselections whose probabilities are close to one. We also show that a single rewind operator is sufficient to achieve tasks that are intractable for quantum computation.
  arXiv  Detail & Related papers  (2022-06-11T06:19:24Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
  We design an algorithm that achieves an $Oleft(mathrmpoly(S,A,log K)sqrtKright)$ regret in contrast to existing bounds. Our result relies on a sequence of new structural lemmas establishing the approximation power, stability, and concentration property of stationary policies.
  arXiv  Detail & Related papers  (2022-03-24T08:14:12Z)
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method [54.93433440034386]
  We find a feasible $epsilon$-suboptimal solution using only $O(epsilon-1)$ PO calls and optimal $O(epsilon-2)$ FO calls. Our experiments confirm that these methods achieve significant speedups over the state-of-the-art, for a problem with costly PO and LMO calls.
  arXiv  Detail & Related papers  (2020-10-05T08:16:56Z)
• The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem [0.0]
  Two-way finite automaton with quantum and classical states (2QCFA) is a model of quantum computation whose quantum part is extremely limited. We show that 2QCFA can recognize the language $L_eq=am bm :m mathbbN$ in expected time and the language $L_pal=w in a,b*:w CFA CFA is a palindrome$ in expected exponential time.
  arXiv  Detail & Related papers  (2020-03-22T12:46:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.