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 条
  • [41] Complexity classes of equivalence problems revisited
    Fortnow, Lance
    Grochow, Joshua A.
    INFORMATION AND COMPUTATION, 2011, 209 (04) : 748 - 763
  • [42] Communication complexity of byzantine agreement, revisited
    Ittai Abraham
    T.-H. Hubert Chan
    Danny Dolev
    Kartik Nayak
    Rafael Pass
    Ling Ren
    Elaine Shi
    Distributed Computing, 2023, 36 : 3 - 28
  • [43] Readability revisited? The implications of text complexity
    Wray, David
    Janan, Dahlia
    CURRICULUM JOURNAL, 2013, 24 (04): : 553 - 562
  • [44] Accidental complexity in multilevel modeling revisited
    Balaban, Mira
    Khitron, Igal
    Maraee, Azzam
    SOFTWARE AND SYSTEMS MODELING, 2022, 21 (02): : 517 - 542
  • [45] Message Complexity of Distributed Algorithms Revisited
    Mann, Behnish
    Arvavid, Alex
    2014 INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED AND GRID COMPUTING (PDGC), 2014, : 417 - 422
  • [46] Accidental complexity in multilevel modeling revisited
    Mira Balaban
    Igal Khitron
    Azzam Maraee
    Software and Systems Modeling, 2022, 21 : 517 - 542
  • [47] Computational Complexity of Natural Morphology Revisited
    Senuma, Hajime
    Aizawa, Akiko
    TRANSACTIONS OF THE ASSOCIATION FOR COMPUTATIONAL LINGUISTICS, 2024, 12 : 649 - 663
  • [48] Communication complexity of byzantine agreement, revisited
    Abraham, Ittai
    Chan, T. -H. Hubert
    Dolev, Danny
    Nayak, Kartik
    Pass, Rafael
    Ren, Ling
    Shi, Elaine
    DISTRIBUTED COMPUTING, 2023, 36 (01) : 3 - 28
  • [49] Communication Complexity of Byzantine Agreement, Revisited
    Abraham, Ittai
    Chan, T-H Hubert
    Dolev, Danny
    Nayak, Kartik
    Pass, Rafael
    Ren, Ling
    Shi, Elaine
    PROCEEDINGS OF THE 2019 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '19), 2019, : 317 - 326
  • [50] The Computational Complexity of the KAKURO Puzzle, Revisited
    Ruepp, Oliver
    Holzer, Markus
    FUN WITH ALGORITHMS, PROCEEDINGS, 2010, 6099 : 319 - +
12345