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 条

[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
[34] On the complementarity of Chaos/Complexity Theory and Dynamic Systems Theory in understanding the second language acquisition process
Larsen-Freeman, Diane
BILINGUALISM-LANGUAGE AND COGNITION, 2007, 10 (01) : 35 - 37
[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

← 1 2 3 4 5 →