Theory of Computing Systems, Volume 41

Volume 41, Number 1, July 2007

S. Barry Cooper, Benedikt Löwe, Peter van Emde Boas:
Theory of Computation at CiE 2005. 1-2
Jan A. Bergstra, C. A. Middelburg:
A Thread Algebra with Multi-Level Strategic Interleaving. 3-32
Pieter Collins:
Optimal Semicomputable Approximations to Reachable and Invariant Sets. 33-48
Amin Farjudian:
Shrad: A Language for Sequential Real Number Computation. 49-105
Klaus Meer:
Some Relations between Approximation Problems and PCPs over the Real Numbers. 107-118
Peter Bro Miltersen:
The Computational Complexity of One-Dimensional Sandpiles. 119-125
Milad Niqui:
Productivity of Edalat-Potts Exact Arithmetic in Constructive Type Theory. 127-154
Ning Zhong:
Computable Analysis of a Boundary-Value Problem for the Korteweg-de Vries Equation. 155-175
Martin Ziegler:
Real Hypercomputation and Continuity. 177-206

Volume 41, Number 2, August 2007

Maciej Liskiewicz, Rüdiger Reischuk:
Preface. 209-210
Matthias P. Krieger:
On the Incompressibility of Monotone DNFs. 211-231
Tomasz Jurdzinski, Krzysztof Lorys:
Leftist Grammars and the Chomsky Hierarchy. 233-256
Daniel Meister:
Polynomial-Space Decidable Membership Problems for Recurrent Systems over Sets of Natural Numbers. 257-289
Holger Spakowski, Rahul Tripathi:
On the Power of Unambiguity in Alternating Machines. 291-326
Till Tantau:
Logspace Optimization Problems and Their Approximability Properties. 327-350
Birgit Schelm:
Average-Case Non-Approximability of Optimisation Problems. 351-368
Michael Brinkmeier:
A Simple and Fast Min-Cut Algorithm. 369-380
Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
Exact Algorithms for Graph Homomorphisms. 381-393

Volume 41, Number 3, October 2007

Rod Downey:
Foreword. 397
Faisal N. Abu-Khzam:
Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems. 399-410
Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, W. Henry Suters:
Crown Structures for Vertex Cover Kernelization. 411-430
Hans-Joachim Böckenhauer, Juraj Hromkovic, Joachim Kneis, Joachim Kupke:
The Parameterized Approximability of TSP with Deadlines. 431-444
Jonathan F. Buss, Tarique Islam:
Algorithms in the W-Hierarchy. 445-457
Liming Cai, Michael R. Fellows, David W. Juedes, Frances A. Rosamond:
The Complexity of Polynomial-Time Approximation. 459-477
Frank K. H. A. Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, Kim Stevens:
An O(2^O(k)n³) FPT Algorithm for the Undirected Feedback Vertex Set Problem. 479-492
Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, Xinhui Wang:
Dynamic Programming for Minimum Steiner Trees. 493-500
Jiong Guo, Rolf Niedermeier, Sebastian Wernicke:
Parameterized Complexity of Vertex Cover Variants. 501-520
Gregory Gutin, Arash Rafiey, Stefan Szeider, Anders Yeo:
The Linear Arrangement Problem Parameterized Above Guaranteed Value. 521-538
Michael T. Hallett, Catherine McCartin:
A Faster FPT Algorithm for the Maximum Agreement Forest Problem. 539-550
Petr Hlinený:
Some Hard Problems on Matroid Spikes. 551-562
Venkatesh Raman, Saket Saurabh, Somnath Sikdar:
Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques. 563-587

Volume 41, Number 4, December 2007

Kunihiko Sadakane:
Compressed Suffix Trees with Full Functionality. 589-607
F. Cedo, Ana Cortés, Ana Ripoll, Miquel A. Senar, Emilio Luque:
The Convergence of Realistic Distributed Load-Balancing Algorithms. 609-618
Janis Voigtländer:
Formal Efficiency Analysis for Tree Transducer Composition. 619-689
Michael Elkin, David Peleg:
The Hardness of Approximating Spanner Problems. 691-729
Li Gao, Grzegorz Malewicz:
Toward Maximizing the Quality of Results of Dependent Tasks Computed Unreliably. 731-752
Elmar Böhler, Henning Schnoor:
The Complexity of the Descriptiveness of Boolean Circuits over Different Sets of Gates. 753-777
Sanjiv Kapoor, Mohammad Sarwat:
Bounded-Diameter Minimum-Cost Graph Problems. 779-794