Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability

被引：4

作者：

Baier, Christel ^{[1
]}

Bertrand, Nathalie ^{[2
]}

Groesser, Marcus ^{[1
]}

机构：

[1] Tech Univ Dresden, Fak Informat, Dresden, Germany

[2] INRIA Rennes Bretagne Atlantique, Rennes, France

来源：

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE | 2009年 / 03期

关键词：

D O I：

10.4204/EPTCS.3.1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word can be defined in different ways: by requiring that (i) the probability for the accepting runs is positive (probable semantics), or (ii) almost all runs are accepting (almost-sure semantics), or (iii) the probability measure of the accepting runs is greater than a certain threshold (threshold semantics). The underlying notion of an accepting run can be defined as for standard omega-automata by means of a Buchi condition or other acceptance conditions, e.g., Rabin or Streett conditions. In this paper, we put the main focus on the probable semantics and provide a summary of the fundamental properties of probabilistic omega-automata concerning expressiveness, efficiency, and decision problems.

引用

页码：3 / 16

页数：14

共 20 条

[1]

Ambainis A., 1998, P 39 S FDN COMP SCI

[2]

Baier C, 2005, IEEE S LOG, P137

[3]

Baier C, 2008, LECT NOTES COMPUT SC, V4962, P287, DOI 10.1007/978-3-540-78499-9_21

[4] On the expressiveness and complexity of randomization in finite state monitors [J].

Chadha, Rohit ;

Sistla, A. Prasad ;

Viswanathan, Mahesh .

TWENTY-THIRD ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2008, :18-+

[5]

Chatterjee K, 2006, LECT NOTES COMPUT SC, V4207, P287

[6] THE COMPLEXITY OF PROBABILISTIC VERIFICATION [J].

COURCOUBETIS, C ;

YANNAKAKIS, M .

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (04) :857-907

[7]

Gradel E., 2001, LECT NOTES COMPUTER, V2500

[8]

Grolier M., 2008, THESIS

[9] On the power of quantum finite state automata [J].

Kondacs, A ;

Watrous, J .

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, :66-75

[10] A SURVEY OF ALGORITHMIC METHODS FOR PARTIALLY OBSERVED MARKOV DECISION PROCESSES [J].

Lovejoy, William S. .

ANNALS OF OPERATIONS RESEARCH, 1991, 28 (01) :47-65

← 1 2 →