Decidable and expressive classes of probabilistic automata

DOI10.1016/j.jcss.2018.09.002zbMath1439.68011OpenAlexW2893448252WikidataQ129189863 ScholiaQ129189863MaRDI QIDQ1740668

Xianqiang Yang

Publication date: 2 May 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2018.09.002

zbMATH Keywords

decidabilityregular languagesemptiness problemuniversality problemhierarchical probabilistic automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reachability problems for Markov chains
• Some observations on the connection between counting and recursion
• Probabilistic Automata with Isolated Cut-Points
• Deciding the value 1 problem for probabilistic leaktight automata
• Decidability of Approximate Skolem Problem and Applications to Logical Verification of Dynamical Properties of Markov Chains
• Decidable and Expressive Classes of Probabilistic Automata
• Decidable Problems for Probabilistic Automata on Infinite Words
• Deciding the Value 1 Problem for Probabilistic Leaktight Automata
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• Probabilistic Büchi Automata with Non-extremal Acceptance Thresholds
• On the expressiveness and complexity of randomization in finite state monitors
• Model Checking Failure-Prone Open Systems Using Probabilistic Automata
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• The complexity of probabilistic verification
• Probabilistic Automata on Infinite Words: Decidability and Undecidability Results
• Probabilistic Automata of Bounded Ambiguity
• Probabilistic ω-automata
• On Decision Problems for Probabilistic Büchi Automata
• Probabilistic automata
• Power of Randomization in Automata on Infinite Strings

This page was built for publication: Decidable and expressive classes of probabilistic automata