Computational Complexity of Dynamic Problems

. This progress report surveys some of my scientific work on part A of the Ph.D.-programme at the Computer Science Department of the University of Aarhus. I give a survey-like introduction to the field of Complexity Theory to which my results bear relevance. I give a general account of my contributions to the field, including the the Dynamic Transitive Closure Problem for spherical st-graphs, the Dynamic Circuit Value Problem, and some dynamic membership problems for formal languages. Contents I. Introduction 3 1. Dynamic Algorithms 2. Overview II. Reachability 6 1. The parallel world 2. Dynamic algorithms for Reachability 3. Planar dags with one source and one sink 4. The result: a detailed account III. Formal Languages 14 1. Other realms 2. Regular Languages 3. Dyck Languages 4. Deterministic context-free languages 5. Conclusion and open problems IV. Finite Index Properties on Graphs of Bounded Tree-width 21 1. Introduction 2. Preliminaries 3. Dynamic Algorithms..