Dynamic complexity theory revisited

被引:15
|
作者
Weber, Volker [1 ]
Schwentick, Thomas [1 ]
机构
[1] Univ Dortmund, Fachbereich Informat, D-44227 Dortmund, Germany
关键词
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 条
  • [31] A Dynamic Ensemble for Second Language Research: Putting Complexity Theory Into Practice
    Hiver, Phil
    Al-Hoorie, Ali H.
    MODERN LANGUAGE JOURNAL, 2016, 100 (04): : 741 - 756
  • [32] Information, complexity and weak chaos in dynamic systems: Theory and measurement methods
    Galatolo, S
    BOLLETTINO DELLA UNIONE MATEMATICA ITALIANA, 2003, 6A (02): : 267 - 270
  • [33] Design theory for dynamic complexity in information infrastructures: the case of building internet
    Hanseth, Ole
    Lyytinen, Kalle
    JOURNAL OF INFORMATION TECHNOLOGY, 2010, 25 (01) : 1 - 19
  • [35] Applying dynamic systems theory and complexity theory methods in psychotherapy research: A systematic literature review
    Klocek, Adam
    Premus, Jan
    Rihacek, Tomas
    PSYCHOTHERAPY RESEARCH, 2023, : 828 - 844
  • [36] Complexity Revisited A different approach to philosophy, Logics and analytics of complexity
    Ghiasi, Mohammad
    2015 9TH INTERNATIONAL CONFERENCE ON APPLICATION OF INFORMATION AND COMMUNICATION TECHNOLOGIES (AICT), 2015, : 553 - 557
  • [37] The auditory dynamic attending theory revisited: A closer look at the pitch comparison task
    Bauer, Anna-Katharina R.
    Jaeger, Manuela
    Thorne, Jeremy D.
    Bendixen, Alexandra
    Debener, Stefan
    BRAIN RESEARCH, 2015, 1626 : 198 - 210
  • [38] Automatic Kolmogorov Complexity and Normality Revisited
    Shen, Alexander
    FUNDAMENTALS OF COMPUTATION THEORY, FCT 2017, 2017, 10472 : 418 - 430
  • [39] Descriptive complexity of computable sequences revisited
    Vereshchagin, Nikolay
    THEORETICAL COMPUTER SCIENCE, 2020, 809 : 531 - 537
  • [40] On the complexity of the identifiable subgraph problem, revisited
    Kratsch, Stefan
    Milanic, Martin
    DISCRETE APPLIED MATHEMATICS, 2017, 226 : 78 - 86