Probabilistic Büchi automata with non-extremal acceptance thresholds

Rohit Chadha; A. Prasad Sistla; Mahesh Viswanathan

doi:10.1007/978-3-642-18275-4_9

Probabilistic Büchi automata with non-extremal acceptance thresholds

Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper investigates the power of Probabilistic Büchi Automata (PBA) when the threshold probability of acceptance is non-extremal, i.e., is a value strictly between 0 and 1. Many practical randomized algorithms are designed to work under non-extremal threshold probabilities and thus it is important to study power of PBAs for such cases. The paper presents a number of surprising expressiveness and decidability results for PBAs when the threshold probability is non-extremal. Some of these results sharply contrast with the results for extremal threshold probabilities. The paper also presents results for Hierarchical PBAs and for an interesting subclass of them called simple PBAs.

Original language	English (US)
Title of host publication	Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings
Pages	103-117
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-18275-4_9
State	Published - 2011
Event	12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2011 - Austin, TX, United States Duration: Jan 23 2011 → Jan 25 2011

Publication series

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

Other

Other	12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2011
Country/Territory	United States
City	Austin, TX
Period	1/23/11 → 1/25/11

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/978-3-642-18275-4_9

Library availability

Discover UIUC Full Text

Cite this

Chadha, R., Sistla, A. P., & Viswanathan, M. (2011). Probabilistic Büchi automata with non-extremal acceptance thresholds. In Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings (pp. 103-117). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6538 LNCS). https://doi.org/10.1007/978-3-642-18275-4_9

Probabilistic Büchi automata with non-extremal acceptance thresholds. / Chadha, Rohit; Sistla, A. Prasad; Viswanathan, Mahesh.
Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings. 2011. p. 103-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6538 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chadha, R, Sistla, AP & Viswanathan, M 2011, Probabilistic Büchi automata with non-extremal acceptance thresholds. in Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6538 LNCS, pp. 103-117, 12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2011, Austin, TX, United States, 1/23/11. https://doi.org/10.1007/978-3-642-18275-4_9

Chadha R, Sistla AP, Viswanathan M. Probabilistic Büchi automata with non-extremal acceptance thresholds. In Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings. 2011. p. 103-117. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-18275-4_9

Chadha, Rohit ; Sistla, A. Prasad ; Viswanathan, Mahesh. / Probabilistic Büchi automata with non-extremal acceptance thresholds. Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings. 2011. pp. 103-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f6b4af7170b94be89c2e57b94cb932cd,

title = "Probabilistic B{\"u}chi automata with non-extremal acceptance thresholds",

abstract = "This paper investigates the power of Probabilistic B{\"u}chi Automata (PBA) when the threshold probability of acceptance is non-extremal, i.e., is a value strictly between 0 and 1. Many practical randomized algorithms are designed to work under non-extremal threshold probabilities and thus it is important to study power of PBAs for such cases. The paper presents a number of surprising expressiveness and decidability results for PBAs when the threshold probability is non-extremal. Some of these results sharply contrast with the results for extremal threshold probabilities. The paper also presents results for Hierarchical PBAs and for an interesting subclass of them called simple PBAs.",

author = "Rohit Chadha and Sistla, {A. Prasad} and Mahesh Viswanathan",

year = "2011",

doi = "10.1007/978-3-642-18275-4_9",

language = "English (US)",

isbn = "9783642182747",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "103--117",

booktitle = "Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings",

note = "12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2011 ; Conference date: 23-01-2011 Through 25-01-2011",

}

TY - GEN

T1 - Probabilistic Büchi automata with non-extremal acceptance thresholds

AU - Chadha, Rohit

AU - Sistla, A. Prasad

AU - Viswanathan, Mahesh

PY - 2011

Y1 - 2011

N2 - This paper investigates the power of Probabilistic Büchi Automata (PBA) when the threshold probability of acceptance is non-extremal, i.e., is a value strictly between 0 and 1. Many practical randomized algorithms are designed to work under non-extremal threshold probabilities and thus it is important to study power of PBAs for such cases. The paper presents a number of surprising expressiveness and decidability results for PBAs when the threshold probability is non-extremal. Some of these results sharply contrast with the results for extremal threshold probabilities. The paper also presents results for Hierarchical PBAs and for an interesting subclass of them called simple PBAs.

AB - This paper investigates the power of Probabilistic Büchi Automata (PBA) when the threshold probability of acceptance is non-extremal, i.e., is a value strictly between 0 and 1. Many practical randomized algorithms are designed to work under non-extremal threshold probabilities and thus it is important to study power of PBAs for such cases. The paper presents a number of surprising expressiveness and decidability results for PBAs when the threshold probability is non-extremal. Some of these results sharply contrast with the results for extremal threshold probabilities. The paper also presents results for Hierarchical PBAs and for an interesting subclass of them called simple PBAs.

UR - http://www.scopus.com/inward/record.url?scp=79251575574&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79251575574&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18275-4_9

DO - 10.1007/978-3-642-18275-4_9

M3 - Conference contribution

AN - SCOPUS:79251575574

SN - 9783642182747

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 103

EP - 117

BT - Verification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings

T2 - 12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2011

Y2 - 23 January 2011 through 25 January 2011

ER -

Probabilistic Büchi automata with non-extremal acceptance thresholds

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this