Polynomially Ambiguous Probabilistic Automata on Restricted Languages

DOI10.4230/LIPICS.ICALP.2019.105MaRDI QIDQ5091267zbMATH OpenOpenAlexFDO

Authors Paul C. Bell

Publication date 21 July 2022

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

zbMATH Keywords

ambiguitybounded languageemptinessprobabilistic finite automataundecidability

Mathematics Subject Classification ID

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

Recommendations

• Polynomially ambiguous probabilistic automata on restricted languages
• Probabilistic automata of bounded ambiguity
• Probabilistic automata of bounded ambiguity

Cites work

• A survey of computational complexity results in systems and control
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Decision problems for probabilistic finite automata on bounded languages
• Generalized Automata and Stochastic Languages
• Homogenization and the polynomial calculus
• scientific article; zbMATH DE number 3978429 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 3513703 (Why is no real title available?)
• scientific article; zbMATH DE number 3572058 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages
• On Post correspondence problem for letter monotonic languages
• On the complexity of the orbit problem
• On the degree of ambiguity of finite automata
• On the equal-subset-sum problem
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Polynomial-time algorithm for the orbit problem
• Probabilistic automata
• Probabilistic automata
• Probabilistic automata of bounded ambiguity
• Scalar ambiguity and freeness in matrix semigroups over bounded languages
• The boundedness of all products of a pair of matrices is undecidable
• The freeness problem over matrix semigroups and bounded languages
• Unbounded-error quantum computation with small space bounds
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• Undecidable problems for probabilistic automata of fixed dimension
• When is containment decidable for probabilistic automata?

Cited in

(4)

• Polynomially ambiguous probabilistic automata on restricted languages
• Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs.
• Polynomially ambiguous unary weighted automata over fields
• Finitely ambiguous and finitely sequential weighted automata over fields

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091267)