Dynamic Complexity Theory Revisited |
| |
| Authors: | Volker Weber Thomas Schwentick |
| |
| Affiliation: | (1) Fachbereich Informatik, Universitat Dortmund, D-44227 Dortmund, Germany |
| |
| Abstract: | 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 D2LREACH(acyclic) can be maintained with first-order updates. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
