Undecidable problems for probabilistic automata of fixed dimension
From MaRDI portal
Publication:1405789
DOI10.1007/s00224-003-1061-2zbMath1039.68061OpenAlexW1728602962MaRDI QIDQ1405789
Vincent Canterini, Blondel, Vincent D.
Publication date: 26 August 2003
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-003-1061-2
Related Items (30)
Polynomially ambiguous probabilistic automata on restricted languages ⋮ Lower bounds on complexity of Lyapunov functions for switched linear systems ⋮ On the decidability of semigroup freeness ⋮ Undecidability of infinite post correspondence problem for instances of size 8 ⋮ Probabilistic Weighted Automata ⋮ When are emptiness and containment decidable for probabilistic automata? ⋮ Recursive stochastic games with positive rewards ⋮ Decision Questions for Probabilistic Automata on Small Alphabets ⋮ The complete realization problem for hidden Markov models: a survey and some new results ⋮ On injectivity of quantum finite automata ⋮ Simple stochastic games with almost-sure energy-parity objectives are in NP and conp ⋮ On the finiteness property for rational matrices ⋮ Efficient algorithms for deciding the type of growth of products of integer matrices ⋮ Decision problems for semi-Thue systems with a few rules ⋮ Probabilistic Acceptors for Languages over Infinite Words ⋮ Freeness properties of weighted and probabilistic automata over bounded languages ⋮ Recursive Markov Decision Processes and Recursive Stochastic Games ⋮ Quantitative simulations by matrices ⋮ Unnamed Item ⋮ Trace Refinement in Labelled Markov Decision Processes ⋮ Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs. ⋮ Polynomially Ambiguous Probabilistic Automata on Restricted Languages ⋮ Acceptance Ambiguity for Quantum Automata ⋮ Quantum Automata Theory – A Review ⋮ Undecidable Problems for Probabilistic Network Programming ⋮ Non-Sturmian sequences of matrices providing the maximum growth rate of matrix products ⋮ Undecidability of infinite post correspondence problem for instances of Size 9 ⋮ On eventual non-negativity and positivity for the weighted sum of powers of matrices ⋮ The exact complexity of the infinite Post Correspondence Problem ⋮ On the undecidability of probabilistic planning and related stochastic optimization problems
This page was built for publication: Undecidable problems for probabilistic automata of fixed dimension
