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
Dietrich Kuske, Markus Lohrey:
Decidable First-Order Theories of One-Step Rewriting in Trace Monoids. 39-81
Sven Kosub:
NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems. 83-113
Enrico Pontelli, Desh Ranjan:
A Simple Optimal Solution for the Temporal Precedence Problem on Pure Pointer Machines. 115-130

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

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

Foreword. 371-372
Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier:
Graph-Modeled Data Clustering: Exact Algorithms for Clique Generation. 373-392
Bala Kalyanasundaram, Mahendran Velauthapillai, John G. Waclawsky:
Unlocking the Advantages of Dynamic Service Selection and Pricing. 393-410
Richard Bruce, Michael Hoffmann, Danny Krizanc, Rajeev Raman:
Efficient Update Strategies for Geometric Computing with Uncertainty. 411-423
Dimitrios Koukopoulos, Marios Mavronicolas, Sotiris E. Nikoletseas, Paul G. Spirakis:
The Impact of Network Structure on the Stability of Greedy Protocols. 425-460
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
Gian Carlo Bongiovanni, Paolo Penna:
XOR-Based Schemes for Fast Parallel IP Lookups. 481-501
Lee-Ad Gottlieb, John E. Savage, Arkady Yerukhimovich:
Efficient Data Storage in Large Nanoarrays. 503-536

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

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