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 条
  • [1] Dynamic complexity theory revisited
    Weber, V
    Schwentick, T
    STACS 2005, PROCEEDINGS, 2005, 3404 : 256 - 268
  • [2] Dynamic Complexity Theory Revisited
    Volker Weber
    Thomas Schwentick
    Theory of Computing Systems, 2007, 40 : 355 - 377
  • [3] Corporate strategy revisited: a view from complexity theory
    Atilio Caldart, Adrian
    Enric Ricart, Joan
    EUROPEAN MANAGEMENT REVIEW, 2004, 1 (01) : 96 - 104
  • [4] Continuous (dynamic) melting theory revisited
    Shaw, DM
    CANADIAN MINERALOGIST, 2000, 38 : 1041 - 1063
  • [5] Dynamic systems theory and the complexity of change
    Thelen, E
    PSYCHOANALYTIC DIALOGUES, 2005, 15 (02) : 255 - 283
  • [6] Spaces allowing Type-2 Complexity Theory revisited
    Schröder, M
    MATHEMATICAL LOGIC QUARTERLY, 2004, 50 (4-5) : 443 - 459
  • [7] THE THEORY OF ROBOT STABILITY IN DYNAMIC ENVIRONMENT REVISITED
    Martynyuk, A. A.
    Khoroshun, A. S.
    Chernienko, A. N.
    INTERNATIONAL APPLIED MECHANICS, 2011, 46 (09) : 1056 - 1061
  • [8] Complexity revisited
    Peter Godfrey-Smith
    Biology & Philosophy, 2017, 32 : 467 - 479
  • [9] Complexity revisited
    Godfrey-Smith, Peter
    BIOLOGY & PHILOSOPHY, 2017, 32 (03) : 467 - 479
  • [10] COMPLEXITY AND DYNAMICS - APPLICATIONS OF DYNAMIC SYSTEM THEORY
    GOTTINGER, HW
    IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1976, 6 (12): : 867 - 873
12345