Polynomially Ambiguous Probabilistic Automata on Restricted Languages
From MaRDI portal
Publication:5091267
DOI10.4230/LIPIcs.ICALP.2019.105OpenAlexW2965171763MaRDI QIDQ5091267
Publication date: 21 July 2022
Full work available at URL: http://doi.org/10.4230/LIPIcs.ICALP.2019.105
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
