A Game Theoretic Approach to the Analysis of Dynamic Networks

被引：14

作者：

Radmacher, Frank G. ^{[1
]}

Thomas, Wolfgang ^{[1
]}

机构：

[1] Rhein Westfal TH Aachen, Lehrstuhl Informat 7, D-52056 Aachen, Germany

来源：

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2008年 / 200卷 / 02期

关键词：

adaptive systems; dynamic networks; dynamic graph problems; model-checking; game theory;

D O I：

10.1016/j.entcs.2008.02.010

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A model of dynamic networks is introduced which incorporates three kinds of network changes: deletion of nodes (by faults or sabotage), restoration of nodes (by actions of "repair"), and creation of nodes (by actions that extend the network). The antagonism between the operations of deletion and restoration resp. creation is modelled by a game between the two agents "Destructor" and "Constructor". In this framework of dynamic model-checking, we consider as specifications ("winning conditions" for Constructor) elementary requirements on connectivity of those networks which are reachable from some initial given network. We show some basic results on the (un-) decidability and hardness of dynamic model-checking problems.

引用

页码：21 / 37

页数：17

共 21 条

[1]

Awerbuch B, 2003, LECT NOTES COMPUT SC, V2719, P1153

[2] Simple routing strategies for adversarial systems [J].

Awerbuch, B ;

Berenbrink, P ;

Brinkmann, A ;

Scheideler, C .

42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2001, :158-167

[3]

Bouajjani A, 2006, LECT NOTES COMPUT SC, V4134, P52

[4]

Corradini A., 2001, ELECT NOTES THEORETI, V51

[5] A reduction from DLP to PDL [J].

Demri, S .

JOURNAL OF LOGIC AND COMPUTATION, 2005, 15 (05) :767-785

[6]

Gadducci F, 2000, LECT NOTES COMPUT SC, V1764, P310

[7]

Goller S, 2007, LECT NOTES COMPUT SC, V4646, P358

[8]

Gradel E., 2001, LECT NOTES COMPUTER, V2500

[9] The dynamic complexity of transitive closure is in DynTC0 [J].

Hesse, W .

THEORETICAL COMPUTER SCIENCE, 2003, 296 (03) :473-485

[10] Complete problems for dynamic complexity classes [J].

Hesse, W ;

Immerman, N .

17TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2002, :313-322

← 1 2 3 →