IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Power of Randomization in Automata on Infinite Strings

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF PBAConcurNew.pdf (303KB) Main article PDF
Title: Power of Randomization in Automata on Infinite Strings
Author(s): Chadha, Rohit; Sistla, A. Parsad; Viswanathan, Mahesh
Subject(s): Randomization regular languages verification open systems
Abstract: Probabilistic B\"{u}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 {\PBA}s topologically, demonstrating that though general {\PBA}s can recognize languages that are not regular, topologically the languages are as simple as $\omega$-regular languages. Finally, we introduce Hierarchical {\PBA}s, which are syntactically restricted forms of {\PBA}s that are tractable and capture exactly the class of $\omega$-regular languages.
Issue Date: 2009
Genre: Technical Report
Type: Text
Language: English
Publication Status: unpublished
Date Available in IDEALS: 2009-06-10

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 181
  • Downloads this Month: 2
  • Downloads Today: 0


My Account


Access Key