Power of Randomization in Automata on Infinite Strings

Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationCONCUR 2009 - Concurrency Theory - 20th International Conference, CONCUR 2009, Proceedings
Pages229-243
Number of pages15
DOIs
StatePublished - 2009
Event20th International Conference on Concurrency Theory, CONCUR 2009 - Bologna, Italy
Duration: Sep 1 2009Sep 4 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5710 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Conference on Concurrency Theory, CONCUR 2009
Country/TerritoryItaly
CityBologna
Period9/1/099/4/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Power of Randomization in Automata on Infinite Strings'. Together they form a unique fingerprint.

Cite this