On the expressiveness and complexity of randomization in finite state monitors

DOI10.1145/1552285.1552287MaRDI QIDQ3452222zbMATH OpenOpenAlexFDO

Authors

Publication date 11 November 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1552285.1552287

zbMATH Keywords

randomizationtopologyprobabilistic automataruntime verificationomega automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Probabilistic Automata for Safety LTL Specifications
• A theory of register monitors
• On the complexity of determinizing monitors
• The complexity of probabilistic verification

Cited in

(16)

• Runtime monitors for Markov decision processes
• Alternating-time stream logic for multi-agent systems
• Selective monitoring
• Probabilistic causes in Markov chains
• Decidable and expressive classes of probabilistic automata
• Probabilistic Büchi automata with non-extremal acceptance thresholds
• scientific article; zbMATH DE number 1884415 (Why is no real title available?)
• Selective monitoring
• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• A theory of register monitors
• Power of Randomization in Automata on Infinite Strings
• On the complexity of determinizing monitors
• The Effect of Tossing Coins in Omega-Automata
• Partial-observation stochastic games, how to win when belief fails
• Probabilistic Acceptors for Languages over Infinite Words
• A survey of partial-observation stochastic parity games

This page was built for publication: On the expressiveness and complexity of randomization in finite state monitors

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