Dynamic complexity theory revisited

被引：15
|
作者：
Weber, Volker [1 ]
Schwentick, Thomas [1 ]
机构：
[1] Univ Dortmund, Fachbereich Informat, D-44227 Dortmund, Germany
来源：
THEORY OF COMPUTING SYSTEMS | 2007年 / 40卷 / 04期
关键词：
D O I：
10.1007/s00224-006-1312-0
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Dynamic complexity investigates the required effort to maintain knowledge about a property of a structure under changing operations. This article introduces a refined notion of dynamic problems which takes the initial structure into account. It develops the basic structural complexity notions accordingly. It also shows that the dynamic version of the LOGCFL-complete problem D(2)LREACH(acyclic) can be maintained with first-order updates.
引用
收藏
页码：355 / 377
页数：23
相关论文
共 50 条
  • [21] Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic
    Iris van de Pol
    Iris van Rooij
    Jakub Szymanik
    Journal of Logic, Language and Information, 2018, 27 : 255 - 294
  • [22] Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic
    van de Pol, Iris
    van Rooij, Iris
    Szymanik, Jakub
    JOURNAL OF LOGIC LANGUAGE AND INFORMATION, 2018, 27 (03) : 255 - 294
  • [23] SIMPLE REACTION-TIME AS A FUNCTION OF RESPONSE COMPLEXITY - MEMORY DRUM THEORY REVISITED
    CHRISTINA, RW
    FISCHMAN, MG
    VERCRUYSSEN, MJP
    ANSON, JG
    JOURNAL OF MOTOR BEHAVIOR, 1982, 14 (04) : 301 - 321
  • [24] THE COMPLEXITY OF STRICT SERIALIZABILITY REVISITED
    KELTER, U
    INFORMATION PROCESSING LETTERS, 1987, 25 (06) : 407 - 411
  • [25] Pleasure and complexity: Berlyne revisited
    Messinger, SM
    JOURNAL OF PSYCHOLOGY, 1998, 132 (05): : 558 - 560
  • [26] Drift and Genome Complexity Revisited
    Whitney, Kenneth D.
    Boussau, Bastien
    Baack, Eric J.
    Garland, Theodore, Jr.
    PLOS GENETICS, 2011, 7 (06):
  • [27] Entropy and the Complexity of Graphs Revisited
    Mowshowitz, Abbe
    Dehmer, Matthias
    ENTROPY, 2012, 14 (03) : 559 - 570
  • [28] ROUNDS IN COMMUNICATION COMPLEXITY REVISITED
    NISAN, N
    WIGDERSON, A
    SIAM JOURNAL ON COMPUTING, 1993, 22 (01) : 211 - 219
  • [29] THE COMPLEXITY OF CONSTRAINT SATISFACTION REVISITED
    MACKWORTH, AK
    FREUDER, EC
    ARTIFICIAL INTELLIGENCE, 1993, 59 (1-2) : 57 - 62
  • [30] Exploring psychological complexity through dynamic systems theory: A complement to reductionism
    Galatzer-Levy, RM
    BEHAVIORAL AND BRAIN SCIENCES, 2005, 28 (02) : 206 - +
12345