Decidable and expressive classes of probabilistic automata

DOI10.1016/J.JCSS.2018.09.002MaRDI QIDQ1740668zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• Decidable and expressive classes of probabilistic automata
• Probabilistic automata on finite words: decidable and undecidable problems
• Power of Randomization in Automata on Infinite Strings
• Power of randomization in automata on infinite strings
• Probabilistic automata over infinite words: expressiveness, efficiency, and decidability

Cites work

• scientific article; zbMATH DE number 3513703 (Why is no real title available?)
• scientific article; zbMATH DE number 3543391 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• 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
• Deciding the value 1 problem for probabilistic leaktight automata
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• Model checking failure-prone open systems using probabilistic automata
• On Decision Problems for Probabilistic Büchi Automata
• On the expressiveness and complexity of randomization in finite state monitors
• Power of randomization in automata on infinite strings
• Probabilistic Büchi automata with non-extremal acceptance thresholds
• Probabilistic automata
• Probabilistic automata of bounded ambiguity
• Probabilistic automata on finite words: decidable and undecidable problems
• Probabilistic automata on infinite words: decidability and undecidability results
• Probabilistic automata with isolated cut-points
• Probabilistic ω-automata
• Reachability problems for Markov chains
• Some observations on the connection between counting and recursion
• The complexity of probabilistic verification

Cited in

(7)

• Properties of probabilistic pushdown automata
• Decidable and expressive classes of probabilistic automata
• Probabilistic ω-automata
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA
• scientific article; zbMATH DE number 465528 (Why is no real title available?)
• When are emptiness and containment decidable for probabilistic automata?
• scientific article; zbMATH DE number 3868623 (Why is no real title available?)

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

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