TY - GEN
T1 - Power of Randomization in Automata on Infinite Strings
AU - Chadha, Rohit
AU - Sistla, A. Prasad
AU - Viswanathan, Mahesh
N1 - Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.
PY - 2009
Y1 - 2009
N2 - Probabilistic Büchi Automata (PBA) are randomized, finite state automata that process input strings of infinite length. Based on the threshold chosen for the acceptance probability, different classes of languages can be defined. In this paper, we present a number of results that clarify the power of such machines and properties of the languages they define. The broad themes we focus on are as follows. We precisely characterize the complexity of the emptiness, universality, and language containment problems for such machines, answering canonical questions central to the use of these models in formal verification. Next, we characterize the languages recognized by PBAs topologically, demonstrating that though general PBAs can recognize languages that are not regular, topologically the languages are as simple as ω-regular languages. Finally, we introduce Hierarchical PBAs, which are syntactically restricted forms of PBAs that are tractable and capture exactly the class of ω-regular languages.
AB - Probabilistic Büchi Automata (PBA) are randomized, finite state automata that process input strings of infinite length. Based on the threshold chosen for the acceptance probability, different classes of languages can be defined. In this paper, we present a number of results that clarify the power of such machines and properties of the languages they define. The broad themes we focus on are as follows. We precisely characterize the complexity of the emptiness, universality, and language containment problems for such machines, answering canonical questions central to the use of these models in formal verification. Next, we characterize the languages recognized by PBAs topologically, demonstrating that though general PBAs can recognize languages that are not regular, topologically the languages are as simple as ω-regular languages. Finally, we introduce Hierarchical PBAs, which are syntactically restricted forms of PBAs that are tractable and capture exactly the class of ω-regular languages.
UR - http://www.scopus.com/inward/record.url?scp=70349862115&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349862115&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04081-8_16
DO - 10.1007/978-3-642-04081-8_16
M3 - Conference contribution
AN - SCOPUS:70349862115
SN - 3642040802
SN - 9783642040801
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 229
EP - 243
BT - CONCUR 2009 - Concurrency Theory - 20th International Conference, CONCUR 2009, Proceedings
T2 - 20th International Conference on Concurrency Theory, CONCUR 2009
Y2 - 1 September 2009 through 4 September 2009
ER -