STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings

by ;
  • ISBN13:


  • ISBN10:


  • Format: Paperback
  • Copyright: 2007-03-22
  • Publisher: Springer Verlag
  • Purchase Benefits
  • Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
List Price: $179.00


This book constitutes the refereed proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007, held in Aachen, Germany in February 2007. The 56 revised full papers presented together with 3 invited papers were carefully reviewed and selected from about 400 submissions. The papers address the whole range of theoretical computer science including algorithms and data structures, automata and formal languages, complexity theory, logic in computer science, semantics, specification, and verification of programs, rewriting and deduction, as well as current challenges like biological computing, quantum computing, and mobile and net computing.

Table of Contents

A calculus and algebra for distributed data managementp. 1
The Buchi complementation sagap. 12
Speed-up techniques for shortest-path computationsp. 23
Compact forbidden-set routingp. 37
A new bound for pure greedy hot potato routingp. 49
Wavelength management in WDM rings to maximize the number of connectionsp. 61
A first investigation of Sturmian treesp. 73
On the size of the universal automaton of a regular languagep. 85
Correlations of partial wordsp. 97
Testing convexity properties of tree coloringsp. 109
Why almost all k-colorable graphs are easyp. 121
On defining integers in the counting hierarchy and proving arithmetic circuit lower boundsp. 133
A new rank technique for formula size lower boundsp. 145
Hard metrics from Cayley graphs of Abelian groupsp. 157
Broadcasting vs. mixing and information dissemination on Cayley graphsp. 163
Light orthogonal networks with constant geometric dilationp. 175
Admissibility in infinite gamesp. 188
Pure stationary optimal strategies in Markov decision processesp. 200
Symmetries and the complexity of pure Nash equilibriump. 212
Computing representations of matroids of bounded branch-widthp. 224
Characterizing minimal interval completionsp. 236
The complexity of unions of disjoint setsp. 248
Kolmogorov-Loveland stochasticity and Kolmogorov complexityp. 260
Bounded-hop energy-efficient broadcast in low-dimensional metrics via coresetsp. 272
On the complexity of affine image matchingp. 284
On fixed point equations over commutative semiringsp. 296
An exponential lower bound for prefix Grobner bases in free monoid ringsp. 308
A cubic kernel for feedback vertex setp. 320
The union of minimal hitting sets : parameterized combinatorial bounds and countingp. 332
An optimal, edges-only fully dynamic algorithm for distance-hereditary graphsp. 344
A search algorithm for the maximal attractor of a cellular automatonp. 356
Universal tilingsp. 367
On the complexity of unary tiling-recognizable picture languagesp. 381
A characterization of strong learnability in the statistical query modelp. 393
On the consistency of discrete Bayesian learningp. 405
VPSPACE and a transfer theorem over the realsp. 417
On symmetric signatures in holographic algorithmsp. 429
Randomly rounding rationals with cardinality constraints and derandomizationsp. 441
Cheating to get better roommates in a random stable matchingp. 453
A deterministic algorithm for summarizing asynchronous streams over a sliding windowp. 465
Arithmetizing classes around NC[superscript 1] and Lp. 477
The polynomially bounded perfect matching problem is in NC[superscript 2]p. 489
Languages with bounded multiparty communication complexityp. 500
New approximation algorithms for minimum cycle bases of graphsp. 512
On completing Latin squaresp. 524
Small space representations for metric min-sum k-clustering and their applicationsp. 536
An optimal tableau-based decision algorithm for propositional neighborhood logicp. 549
Bounded-variable fragments of hybrid logicsp. 561
Rank-1 modal logics are coalgebraicp. 573
An efficient quantum algorithm for the hidden subgroup problem in extraspecial groupsp. 586
Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problemp. 598
Quantum network codingp. 610
Reachability in unions of commutative rewriting systems is decidablep. 622
Associative-commutative deducibility constraintsp. 634
On the automatic analysis of recursive security protocols with XORp. 646
Improved online algorithms for the sorting buffer problemp. 658
Cost sharing methods for makespan and completion time schedulingp. 670
Planar graphs : logical complexity and parallel isomorphism testsp. 682
Enumerating all solutions for constraint satisfaction problemsp. 694
Table of Contents provided by Blackwell. All Rights Reserved.

Rewards Program

Write a Review