Model checking strategic abilities of agents under incomplete information

被引：0

作者：

Jamroga, W ^{[1
]}

Dix, E ^{[1
]}

机构：

[1] Tech Univ Clausthal, Dept Comp Sci, D-38678 Clausthal Zellerfeld, Germany

来源：

THEORETICAL COMPUTER SCIENCE, PROCEEDINGS | 2005年 / 3701卷

关键词：

computational complexity; multi-agent systems; temporal logic; strategic ability; games with incomplete information; TIME TEMPORAL LOGIC; SYSTEMS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we introduce and study the complexity of model checking alternating-time temporal logic (ATL) with imperfect information, using a fine-structured complexity measure. While ATL model checking with perfect information is linear in the size of the model when the number of agents is considered fixed, this is no longer true when the number of agents is considered parameters of the problem (fine structure). Combining it with results from our previous papers, we get the surprising result that checking strategic abilities of agents under both perfect and imperfect information belong to the same complexity class: both problems are Sigma(P)(2)-complete.

引用

页码：295 / 308

页数：14

共 21 条

[1] Alternating-time temporal logic [J].

Alur, R ;

Henzinger, TA ;

Kupferman, O .

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, :100-109

[2]

Alur R, 1998, LECT NOTES COMPUT SC, V1536, P23, DOI 10.1007/3-540-49213-5_2

[3] Alternating-time temporal logic [J].

Alur, R ;

Henzinger, TA ;

Kupferman, O .

JOURNAL OF THE ACM, 2002, 49 (05) :672-713

[4] JMOCHA: A model checking tool that exploits design structure [J].

Alur, R ;

De Alfaro, L ;

Grosu, R ;

Henzinger, TA ;

Kang, M ;

Kirsch, CM ;

Majumdar, R ;

Mang, F ;

Wang, BY .

PROCEEDINGS OF THE 23RD INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, 2001, :835-836

[5]

Alur R, 1998, LECT NOTES COMPUT SC, V1427, P521, DOI 10.1007/BFb0028774

[6] AUTOMATIC VERIFICATION OF FINITE-STATE CONCURRENT SYSTEMS USING TEMPORAL LOGIC SPECIFICATIONS [J].

CLARKE, EM ;

EMERSON, EA ;

SISTLA, AP .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1986, 8 (02) :244-263

[7]

de Alfaro L., 2001, CONCUR'01, LNCS, V2154, P566

[8]

DEALFARO L, 2000, LECT NOTES COMPUTER, V1877, P458

[9]

Emerson E.A., 1990, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, VB, P995, DOI [DOI 10.1016/B978-0-444-88074-1.50021-4, 10.1016/B978-0-444-88074-1.50021-4.]

[10]

EMERSON EA, 1982, P ANN ACM S PRINC PR, P151

← 1 2 3 →