Rohit Chadha ; A. Prasad Sistla ; Mahesh Viswanathan - Power of Randomization in Automata on Infinite Strings

lmcs:948 - Logical Methods in Computer Science, September 29, 2011, Volume 7, Issue 3 - https://doi.org/10.2168/LMCS-7(3:22)2011
Power of Randomization in Automata on Infinite StringsArticle

Authors: Rohit Chadha ; A. Prasad Sistla ; Mahesh Viswanathan

    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 present results on the decidability and precise complexity of the emptiness, universality and language containment problems for such machines, thus answering 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 \omega-regular languages. Finally, we introduce Hierarchical PBAs, which are syntactically restricted forms of PBAs that are tractable and capture exactly the class of \omega-regular languages.


    Volume: Volume 7, Issue 3
    Published on: September 29, 2011
    Imported on: March 8, 2011
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science,F.4.3,D.2.4,F.1.1,F.1.2
    Funding:
      Source : OpenAIRE Graph
    • SGER: Monitoring Off-the-shelf Components; Funder: National Science Foundation; Code: 0742686

    6 Documents citing this article

    Consultation statistics

    This page has been seen 1069 times.
    This article's PDF has been downloaded 463 times.