+612 9045 4394
Stacs 2004 : 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings - Volker Diekert

Stacs 2004

21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings

By: Volker Diekert (Editor), Michel Habib (Editor)

Paperback Published: 18th March 2004
ISBN: 9783540212362
Number Of Pages: 660

Share This Book:


or 4 easy payments of $48.19 with Learn more
Ships in 5 to 9 business days

The Symposium on Theoretical Aspects of Computer Science (STACS) is alt- nately held in France and in Germany. The conference of March 25-27, 2004 at the Corum, Montpellier was the twenty-?rst in this series. Previous meetings took place in Paris (1984), Saarbruc ] ken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wurzburg ] (1993), Caen(1994), Munc ] hen(1995), Grenoble(1996), Lub ] eck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), Antibes (2002), and Berlin (2003). The symposium looks back at a remarkable tradition of over 20 years. The interest in STACS has been increasing continuously during recent years and has turned it into one of the most signi?cant conferences in theoretical computer science. The STACS 2004 call for papers led to more than 200 submissions from all over the world. Thereviewingprocesswasextremelyhard: morethan800reviewsweredone. We would like to thank the program committee and all external referees for the valuable work they put into the reviewing process of this conference. We had a two-day meeting for the program committee in Montpellier during November 21-22, 2003. Just 54 papers (i.e., 27% of the submissions) could be accepted, as we wanted to keep the conference in its standard format with only two parallel sessions. This strict selection guaranteed the very high scienti?c quality of the conference.

Approximation schemes for metric clustering problemsp. 1
Positional determinacy of infinite gamesp. 4
Individual communication complexityp. 19
The complexity of satisfiabilty problems over finite latticesp. 31
Constant width planar computation characterizes ACC[superscript 0]p. 44
A simple and fast approach for solving problems on planar graphsp. 56
Sum-multicoloring on pathsp. 68
Matching algorithms are fast in sparse random graphsp. 81
Algebraic results on quantum automatap. 93
Quantum identification of boolean oraclesp. 105
Local limit distributions in pattern statistics : beyond the Markovian modelsp. 117
A discontinuity in pattern inferencep. 129
Algorithms for SAT based on search in hamming ballsp. 141
Identifying efficiently solvable cases of max CSPp. 152
The complexity of boolean constraint isomorphismp. 164
On minimizing the total weighted tardiness on a single machinep. 176
Online competitive algorithms for maximizing weighted throughput of unit jobsp. 187
Optimal and online preemptive scheduling on uniformly related machinesp. 199
Parallel prefetching and caching is hardp. 211
Strongly stable matchings in time O(nm) and extension to the hospitals-residents problemp. 222
Approximation algorithms for minimizing average distortionp. 234
Digraphs exploration with little memoryp. 246
Approximate patch coloring with applications to wavelength assignment in WDM optical networksp. 258
An algorithmic view on OVSF code assignmentp. 270
The syntactic graph of a sofic shiftp. 282
Periodicity and unbordered wordsp. 294
Desert automata and the finite substitution problemp. 305
Satisfiability problems complete for deterministic logarithmic spacep. 317
A logspace approximation scheme for the shortest path problem for graphs with bounded independence numberp. 326
The minimal logically-defined NP-complete problemp. 338
Solving the 2-disjoint paths problem in nearly linear timep. 350
Simpler computation of single-source shortest paths in linear average timep. 362
Lattices with many cycles are densep. 370
Automata-based analysis of recursive cryptographic protocolsp. 382
On minimum circular arrangementp. 394
Integral symmetric 2-commodity flowsp. 406
Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networksp. 418
On the expressiveness of deterministic transducers over infinite treesp. 428
Definability and regularity in automatic structuresp. 440
Active context-free gamesp. 452
Worst case performance of an approximation algorithm for asymmetric TSPp. 465
On visibility representation of plane graphsp. 477
Topology matters : smoothed competitiveness of metrical task systemsp. 489
A randomized competitive algorithm for evaluating priced and/or treesp. 501
The plurality problem with three colorsp. 513
A measured collapse of the modal [mu]-calculus alternation hierarchyp. 522
An information theoretic lower bound for broadcasting in radio networksp. 534
A new model for selfish routingp. 547
Broadcast in the rendezvous modelp. 559
Time-space tradeoff in derandomizing probabilistic logspacep. 571
What can be efficiently reduced to the k-random strings?p. 584
Regular language matching and other decidable cases of the satisfiability problem for constraints between regular open termsp. 596
Deterministic truthful approximation mechanisms for scheduling related machinesp. 608
The expected competitive ratio for weighted completion time schedulingp. 620
Effective strong dimension in algorithmic information and computational complexityp. 632
A lower bound on the competitive ratio of truthful auctionsp. 644
Errata to analysis of the harmonic algorithm for three serversp. 656
Author indexp. 657
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540212362
ISBN-10: 3540212361
Series: Lecture Notes in Computer Science,
Audience: General
Format: Paperback
Language: English
Number Of Pages: 660
Published: 18th March 2004
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.45
Weight (kg): 0.93