Probabilistic automata on finite words: decidable and undecidable problems

DOI10.1007/978-3-642-14162-1_44zbMATH Open1288.68156OpenAlexW1574229394MaRDI QIDQ3587465FDOQ3587465

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

Recommendations

• Probabilistic automata on infinite words: decidability and undecidability results
• Decidable problems for probabilistic automata on infinite words
• Probabilistic automata of bounded ambiguity
• Deciding the value 1 problem for probabilistic leaktight automata
• Probabilistic automata of bounded ambiguity

Mathematics Subject Classification ID

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

Cited In (43)

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

This page was built for publication: Probabilistic automata on finite words: decidable and undecidable problems

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