STACS 2003: 20th Annual Symposium on Theoretical Aspects of Computer Science Berlin, Germany, February 27 – March 1, 2003 Proceedings

Victor Vianu (auth.), Helmut Alt, Michel Habib (eds.)3540006230, 9783540006237

This book constitutes the refereed proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, held in Berlin, Germany in February/March 2003.

The 58 revised full papers presented together with 2 invited papers were carefully reviewed and selected from 253 submissions. The papers address the whole range of theoretical computer science including algorithms and data structures, automata and formal languages, complexity theory, semantics, logic in computer science, as well as current challenges like biological computing, quantum computing, and mobile and net computing.

---

Table of contents :
Logic as a Query Language: From Frege to XML….Pages 1-12
How Does Computer Science Change Molecular Biology?….Pages 13-13
Improved Compact Visibility Representation of Planar Graph via Schnyder’s Realizer….Pages 14-25
Rectangle Visibility Graphs: Characterization, Construction, and Compaction….Pages 26-37
Approximating Geometric Bottleneck Shortest Paths….Pages 38-49
Optimization in Arrangements….Pages 50-61
Complete Classifications for the Communication Complexity of Regular Languages….Pages 62-73
The Commutation with Codes and Ternary Sets of Words….Pages 74-84
On the Confluence of Linear Shallow Term Rewrite Systems….Pages 85-96
Wadge Degrees of ω-Languages of Deterministic Turing Machines….Pages 97-108
Faster Deterministic Broadcasting in Ad Hoc Radio Networks….Pages 109-120
Private Computations in Networks: Topology versus Randomness….Pages 121-132
On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements….Pages 133-144
Lattice Reduction by Random Sampling and Birthday Methods….Pages 145-156
On the Ultimate Complexity of Factorials….Pages 157-166
On the Effective Jordan Decomposability….Pages 167-178
Fast Algorithms for Extended Regular Expression Matching and Searching….Pages 179-190
Algorithms for Transposition Invariant String Matching (Extended Abstract)….Pages 191-202
On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets….Pages 203-211
Some Results on Derandomization….Pages 212-222
On the Representation of Boolean Predicates of the Diffie-Hellman Function….Pages 223-233
Quantum Circuits with Unbounded Fan-out….Pages 234-246
Analysis of the Harmonic Algorithm for Three Servers….Pages 247-259
Non-clairvoyant Scheduling for Minimizing Mean Slowdown….Pages 260-270
Space Efficient Hash Tables with Worst Case Constant Access Time….Pages 271-282
Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure….Pages 283-294
Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs….Pages 295-306
Randomness versus Nondeterminism for Read-Once and Read-k Branching Programs….Pages 307-318
Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids….Pages 319-330
Algebraic Characterizations of Small Classes of Boolean Functions….Pages 331-342
On the Difficulty of Some Shortest Path Problems….Pages 343-354
Representing Graph Metrics with Fewest Edges….Pages 355-366
Computing Shortest Paths with Uncertainty….Pages 367-378
Solving Order Constraints in Logarithmic Space….Pages 379-390
The Inversion Problem for Computable Linear Operators….Pages 391-402
Algebras of Minimal Rank over Arbitrary Fields….Pages 403-414
Evolutionary Algorithms and the Maximum Matching Problem….Pages 415-426
Alternative Algorithms for Counting All Matchings in Graphs….Pages 427-438
Strong Stability in the Hospitals/Residents Problem….Pages 439-450
The Inference Problem for Propositional Circumscription of Afine Formulas Is coNP-Complete….Pages 451-462
Decidable Theories of Cayley-Graphs….Pages 463-474
The Complexity of Resolution with Generalized Symmetry Rules….Pages 475-486
Colouring Random Graphs in Expected Polynomial Time….Pages 487-498
An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation….Pages 499-510
Finding Large Independent Sets in Polynomial Expected Time….Pages 511-522
Distributed Soft Path Coloring….Pages 523-534
Competing Provers Yield Improved Karp-Lipton Collapse Results….Pages 535-546
One Bit of Advice….Pages 547-558
Strong Reductions and Immunity for Exponential Time….Pages 559-570
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers….Pages 571-582
Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem….Pages 583-595
Cake-Cutting Is Not a Piece of Cake….Pages 596-607
The Price of Truth: Frugality in Truthful Mechanisms….Pages 608-619
Untameable Timed Automata!….Pages 620-631
The Intrinsic Universality Problem of One-Dimensional Cellular Automata….Pages 632-641
On Sand Automata….Pages 642-653
Adaptive Sorting and the Information Theoretic Lower Bound….Pages 654-662
A Discrete Subexponential Algorithm for Parity Games….Pages 663-674
Cryptographically Sound and Machine-Assisted Verification of Security Protocols….Pages 675-686
Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic….Pages 687-698