Probabilistic Automata on Finite Words: Decidable and Undecidable Problems

DOI10.1007/978-3-642-14162-1_44zbMath1288.68156MaRDI 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

68Q45: Formal languages and automata

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

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