Polynomially Ambiguous Probabilistic Automata on Restricted Languages

DOI10.4230/LIPIcs.ICALP.2019.105OpenAlexW2965171763MaRDI QIDQ5091267

Paul C. Bell

Publication date: 21 July 2022

Full work available at URL: http://doi.org/10.4230/LIPIcs.ICALP.2019.105

zbMATH Keywords

undecidabilityambiguitybounded languageprobabilistic finite automataemptiness

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (4)

Polynomially ambiguous probabilistic automata on restricted languages ⋮ Polynomially ambiguous unary weighted automata over fields ⋮ Decision Questions for Probabilistic Automata on Small Alphabets ⋮ Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unbounded-error quantum computation with small space bounds
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Probabilistic automata
• On the degree of ambiguity of finite automata
• On the equal-subset-sum problem
• Undecidable problems for probabilistic automata of fixed dimension
• Homogenization and the polynomial calculus
• The boundedness of all products of a pair of matrices is undecidable
• The freeness problem over matrix semigroups and bounded languages
• On Post correspondence problem for letter monotonic languages
• Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• On the Complexity of the Orbit Problem
• Polynomial-time algorithm for the orbit problem
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Decision Problems for Probabilistic Finite Automata on Bounded Languages
• Probabilistic Automata of Bounded Ambiguity
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages
• Probabilistic automata
• Generalized Automata and Stochastic Languages
• A survey of computational complexity results in systems and control

This page was built for publication: Polynomially Ambiguous Probabilistic Automata on Restricted Languages