Probabilistic Automata on Finite Words: Decidable and Undecidable Problems

DOI10.1007/978-3-642-14162-1_44zbMath1288.68156OpenAlexW1574229394MaRDI QIDQ3587465

Youssouf Oualhadj, Hugo Gimbert

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14162-1_44

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (36)

Polynomially ambiguous probabilistic automata on restricted languages ⋮ What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives ⋮ Measure Quantifier in Monadic Second Order Logic ⋮ Reachability analysis of quantum Markov decision processes ⋮ Unnamed Item ⋮ Stochastization of Weighted Automata ⋮ Decision Questions for Probabilistic Automata on Small Alphabets ⋮ Unnamed Item ⋮ Recurrence and transience for finite probabilistic tables ⋮ Controlling a random population ⋮ Ambiguity, weakness, and regularity in probabilistic Büchi automata ⋮ Probabilistic opacity for Markov decision processes ⋮ Diagnosis and degradation control for probabilistic systems ⋮ Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Decidable and expressive classes of probabilistic automata ⋮ The complexity of synchronizing Markov decision processes ⋮ A survey of partial-observation stochastic parity games ⋮ Profinite techniques for probabilistic automata and the Markov monoid algorithm ⋮ Partial-Observation Stochastic Games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Distributed Synthesis in Continuous Time ⋮ Deciding Maxmin Reachability in Half-Blind Stochastic Games ⋮ Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs. ⋮ Unnamed Item ⋮ Probabilistic automata of bounded ambiguity ⋮ Bisimulation metrics and norms for real-weighted automata ⋮ Unnamed Item ⋮ Probabilistic Automata of Bounded Ambiguity ⋮ Undecidable Problems for Probabilistic Network Programming ⋮ POMDPs under probabilistic semantics ⋮ On eventual non-negativity and positivity for the weighted sum of powers of matrices

This page was built for publication: Probabilistic Automata on Finite Words: Decidable and Undecidable Problems