Theory of Computing Systems, Volume 40

Volume 40, Number 1, February 2007

• Valérie Berthé, Michel Rigo:
  Odometers on Regular Languages. 1-31
  Electronic Edition (link) BibTeX
• Igor Shparlinski, Ron Steinfeld:
  Chinese Remaindering with Multiplicative Noise. 33-41
  Electronic Edition (link) BibTeX
• Vesa Halava, Tero Harju, Juhani Karhumäki:
  The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems. 43-54
  Electronic Edition (link) BibTeX
• Haim Kaplan, Tova Milo, Ronen Shabo:
  Compact Labeling Scheme for XML Ancestor Queries. 55-99
  Electronic Edition (link) BibTeX
• Matthias Krause:
  OBDD-Based Cryptanalysis of Oblivious Keystream Generators. 101-121
  Electronic Edition (link) BibTeX

Volume 40, Number 2, February 2007

• Yung H. Tsin:
  A Simple 3-Edge-Connected Component Algorithm. 125-142
  Electronic Edition (link) BibTeX
• Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro:
  Rendezvous and Election of Mobile Agents: Impact of Sense of Direction. 143-162
  Electronic Edition (link) BibTeX
• Frank Drewes, Johanna Högberg:
  Query Learning of Regular Tree Languages: How to Avoid Dead States. 163-185
  Electronic Edition (link) BibTeX
• Guang Xu, Jinhui Xu:
  Constant Approximation Algorithms for Rectangle Stabbing and Related Problems. 187-204
  Electronic Edition (link) BibTeX

Volume 40, Number 3, April 2007

• Peter J. Grabner, Michel Rigo:
  Distribution of Additive Functions with Respect to Numeration Systems on Regular Languages. 205-223
  Electronic Edition (link) BibTeX
• Euripides Markou, Andrzej Pelc:
  Efficient Exploration of Faulty Trees. 225-247
  Electronic Edition (link) BibTeX
• Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe:
  Randomized Algorithms for 3-SAT. 249-262
  Electronic Edition (link) BibTeX
• Ondrej Klíma, Pascal Tesson, Denis Thérien:
  Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups. 263-297
  Electronic Edition (link) BibTeX

Volume 40, Number 4, June 2007

• Volker Diekert, Bruno Durand:
  Foreword. 301
  Electronic Edition (link) BibTeX
• Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid:
  Characterizing TC⁰ in Terms of Infinite Groups. 303-325
  Electronic Edition (link) BibTeX
• Gianni Franceschini:
  Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves. 327-353
  Electronic Edition (link) BibTeX
• Volker Weber, Thomas Schwentick:
  Dynamic Complexity Theory Revisited. 355-377
  Electronic Edition (link) BibTeX
• Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
  Robust Polynomials and Quantum Algorithms. 379-395
  Electronic Edition (link) BibTeX
• Emmanuel Jeandel:
  Topological Automata. 397-407
  Electronic Edition (link) BibTeX
• Victor Poupet:
  Cellular Automata: Real-Time Equivalence between One-Dimensional Neighborhoods. 409-421
  Electronic Edition (link) BibTeX
• Nir Andelman, Yossi Azar, Motti Sorani:
  Truthful Approximation Mechanisms for Scheduling Selfish Related Machines. 423-436
  Electronic Edition (link) BibTeX
• Dietmar Berwanger, Erich Grädel, Giacomo Lenzi:
  The Variable Hierarchy of the µ-Calculus Is Strict. 437-466
  Electronic Edition (link) BibTeX
• Benjamin Doerr:
  Roundings Respecting Hard Constraints. 467-483
  Electronic Edition (link) BibTeX
• Telikepalli Kavitha, Kurt Mehlhorn:
  Algorithms to Compute Minimum Cycle Basis in Directed Graphs. 485-505
  Electronic Edition (link) BibTeX
• Fabio Burderi, Antonio Restivo:
  Varieties of Codes and Kraft Inequality. 507-520
  Electronic Edition (link) BibTeX
• Michal Kunc:
  The Power of Commuting with Finite Sets of Words. 521-551
  Electronic Edition (link) BibTeX
• Gregorio Malajovich, Klaus Meer:
  Computing Minimal Multi-Homogeneous Bezout Numbers Is Hard. 553-570
  Electronic Edition (link) BibTeX