Power of randomization in automata on infinite strings

DOI10.2168/LMCS-7(3:22)2011MaRDI QIDQ5895526zbMATH OpenFDO

Authors Rohit Chadha, A. Sistla Prasad, Mahesh Viswanathan

Publication date 2 April 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/LMCS-7(3:22)2011

zbMATH Keywords

automata on infinite stringsdecidabilityexpressivenessomega-regular languagesprobabilistic monitorsrandomization

Mathematics Subject Classification ID

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

Recommendations

• Power of Randomization in Automata on Infinite Strings
• Probabilistic Büchi automata with non-extremal acceptance thresholds
• On Decision Problems for Probabilistic Büchi Automata
• scientific article; zbMATH DE number 1822394
• Probabilistic automata over infinite words: expressiveness, efficiency, and decidability

Cited in

(11)

• Decidable and expressive classes of probabilistic automata
• Ambiguity, weakness, and regularity in probabilistic Büchi automata
• Random strings and truth-table degrees of Turing complete c.e. sets
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• Limits on the Computational Power of Random Strings
• Probabilistic Büchi automata with non-extremal acceptance thresholds
• scientific article; zbMATH DE number 1822394 (Why is no real title available?)
• scientific article; zbMATH DE number 1439861 (Why is no real title available?)
• On Decision Problems for Probabilistic Büchi Automata
• Power of Randomization in Automata on Infinite Strings
• Windable heads and recognizing \textsf{NL} with constant randomness

This page was built for publication: Power of randomization in automata on infinite strings

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