Theory of Computing Systems, Volume 38

Volume 38, Number 1, January 2005

• Manfred Droste, Christian Pech, Heiko Vogler:
  A Kleene Theorem for Weighted Tree Automata. 1-38
  Electronic Edition (link) BibTeX
• Dietrich Kuske, Markus Lohrey:
  Decidable First-Order Theories of One-Step Rewriting in Trace Monoids. 39-81
  Electronic Edition (link) BibTeX
• Sven Kosub:
  NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems. 83-113
  Electronic Edition (link) BibTeX
• Enrico Pontelli, Desh Ranjan:
  A Simple Optimal Solution for the Temporal Precedence Problem on Pure Pointer Machines. 115-130
  Electronic Edition (link) BibTeX

Volume 38, Number 2, February 2005

• Helmut Alt:
  Foreword. 133
  Electronic Edition (link) BibTeX
• Pascal Tesson, Denis Thérien:
  Complete Classifications for the Communication Complexity of Regular Languages. 135-159
  Electronic Edition (link) BibTeX
• Juhani Karhumäki, Michel Latteux, Ion Petre:
  Commutation with Ternary Sets of Words. 161-169
  Electronic Edition (link) BibTeX
• Stefan Szeider:
  The Complexity of Resolution with Generalized Symmetry Rules. 171-188
  Electronic Edition (link) BibTeX
• Xizhong Zheng, Robert Rettinger:
  Effective Jordan Decomposition. 189-209
  Electronic Edition (link) BibTeX
• Harry Buhrman, Lance Fortnow, Aduri Pavan:
  Some Results on Derandomization. 211-227
  Electronic Edition (link) BibTeX
• Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul G. Spirakis:
  Space Efficient Hash Tables with Worst Case Constant Access Time. 229-248
  Electronic Edition (link) BibTeX

Volume 38, Number 3, May 2005

• Foreword. 251
  Electronic Edition (link) BibTeX
• Therese C. Biedl, Dana F. Wilkinson:
  Bounded-Degree Independent Sets in Planar Graphs. 253-278
  Electronic Edition (link) BibTeX
• Christoph Ambühl, Uli Wagner:
  The Clique Problem in Intersection Graphs of Ellipses and Triangles. 279-292
  Electronic Edition (link) BibTeX
• Christoph Buchheim, Seok-Hee Hong:
  Crossing Minimization for Symmetries. 293-311
  Electronic Edition (link) BibTeX
• Cesim Erten, Stephen G. Kobourov:
  Simultaneous Embedding of a Planar Graph and Its Dual on the Grid. 313-327
  Electronic Edition (link) BibTeX
• Adi Avidor, Uri Zwick:
  Approximating MIN 2-SAT and MIN 3-SAT. 329-345
  Electronic Edition (link) BibTeX
• Tomasz Jurdzinski, Grzegorz Stachowiak:
  Probabilistic Algorithms for the Wake-Up Problem in Single-Hop Radio Networks. 347-367
  Electronic Edition (link) BibTeX

Volume 38, Number 4, July 2005

• Foreword. 371-372
  Electronic Edition (link) BibTeX
• Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier:
  Graph-Modeled Data Clustering: Exact Algorithms for Clique Generation. 373-392
  Electronic Edition (link) BibTeX
• Bala Kalyanasundaram, Mahendran Velauthapillai, John G. Waclawsky:
  Unlocking the Advantages of Dynamic Service Selection and Pricing. 393-410
  Electronic Edition (link) BibTeX
• Richard Bruce, Michael Hoffmann, Danny Krizanc, Rajeev Raman:
  Efficient Update Strategies for Geometric Computing with Uncertainty. 411-423
  Electronic Edition (link) BibTeX
• Dimitrios Koukopoulos, Marios Mavronicolas, Sotiris E. Nikoletseas, Paul G. Spirakis:
  The Impact of Network Structure on the Stability of Greedy Protocols. 425-460
  Electronic Edition (link) BibTeX
• Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong:
  On-line Stream Merging with Max Span and Min Coverage. 461-479
  Electronic Edition (link) BibTeX
• Gian Carlo Bongiovanni, Paolo Penna:
  XOR-Based Schemes for Fast Parallel IP Lookups. 481-501
  Electronic Edition (link) BibTeX
• Lee-Ad Gottlieb, John E. Savage, Arkady Yerukhimovich:
  Efficient Data Storage in Large Nanoarrays. 503-536
  Electronic Edition (link) BibTeX

Volume 38, Number 5, September 2005

• Giuseppe Prencipe:
  The Effect of Synchronicity on the Behavior of Autonomous Mobile Robots. 539-558
  Electronic Edition (link) BibTeX
• John M. Hitchcock:
  Correspondence Principles for Effective Dimensions. 559-571
  Electronic Edition (link) BibTeX
• Frédéric Magniez:
  Multi-Linearity Self-Testing with Relative Error. 573-591
  Electronic Edition (link) BibTeX
• Véronique Bruyère, Olivier Carton:
  Hierarchy Among Automata on Linear Orderings. 593-621
  Electronic Edition (link) BibTeX
• Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Raffaele Mosca:
  New Graph Classes of Bounded Clique-Width. 623-645
  Electronic Edition (link) BibTeX
• K. Subramani:
  Tractable Fragments of Presburger Arithmetic. 647-668
  Electronic Edition (link) BibTeX

Volume 38, Number 6, November 2005

• Beate Bollig, Philipp Woelfel:
  A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications. 671-685
  Electronic Edition (link) BibTeX
• Irene Finocchi, Rossella Petreschi:
  Structure-Preserving Hierarchical Decompositions. 687-700
  Electronic Edition (link) BibTeX
• Xizhong Zheng, Robert Rettinger, Romain Gengler:
  Closure Properties of Real Number Classes under CBV Functions. 701-729
  Electronic Edition (link) BibTeX
• Richard Edwin Stearns, Harry B. Hunt III:
  Resource Bounds and Subproblem Independence. 731-761
  Electronic Edition (link) BibTeX
• Marc Demange, Vangelis Th. Paschos:
  Improved Approximations for Weighted and Unweighted Graph Problems. 763-787
  Electronic Edition (link) BibTeX