Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs.

DOI10.4230/LIPIcs.CONCUR.2020.22OpenAlexW3082263294MaRDI QIDQ5089287

Paul C. Bell, Pavel Semukhin

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/2002.07660

zbMATH Keywords

probabilistic finite automatacutpoint isolation problemletter-bounded context-free languages

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Decision Questions for Probabilistic Automata on Small Alphabets, Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs., Bounds for synchronizing Markov decision processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Numerical semigroups.
• On the degree of ambiguity of finite automata
• Undecidable problems for probabilistic automata of fixed dimension
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Freeness properties of weighted and probabilistic automata over bounded languages
• Semigroups, Presburger formulas, and languages
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• COMPUTING JORDAN NORMAL FORMS EXACTLY FOR COMMUTING MATRICES IN POLYNOMIAL TIME
• Decision Problems for Probabilistic Finite Automata on Bounded Languages
• Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs.
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• Probabilistic Automata of Bounded Ambiguity
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages
• On Context-Free Languages
• Probabilistic automata
• Generalized Automata and Stochastic Languages
• Algorithms in real algebraic geometry