University of Illinois Urbana-Champaign

Power of Randomization in Automata on Infinite Strings

Chadha, Rohit; Sistla, A. Parsad; Viswanathan, Mahesh

Content Files
PBAConcurNew.pdf

Permalink

https://hdl.handle.net/2142/12121

Description

Title
Power of Randomization in Automata on Infinite Strings
Author(s)
  • Chadha, Rohit
  • Sistla, A. Parsad
  • Viswanathan, Mahesh
Issue Date
2009
Keyword(s)
  • Randomization
  • regular languages
  • verification
  • open systems
Date of Ingest
2009-06-10T20:40:04Z
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."
Type of Resource
text
Genre of Resource
Technical Report
Language
en
Permalink
http://hdl.handle.net/2142/12121

Owning Collections

Illinois Research and Scholarship (Open Collection) PRIMARY
This is the default collection for all research and scholarship developed by faculty, staff, or students at the University of Illinois at Urbana-Champaign