+612 9045 4394
Stacs 99 : 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999 Proceedings - Christoph Meinel

Stacs 99

16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999 Proceedings

By: Christoph Meinel (Editor), Sophie Tison (Editor)


Published: 22nd February 1999
Ships: 15 business days
15 business days
or 4 easy payments of $45.32 with Learn more

The Symposium on Theoretical Aspects of Computer Science (STACS) is held annually, alternating between France and Germany. The current volume cons- tutes the proceedings of the 16th STACS conference, organized jointly by the Special Interest Group for Theoretical Computer Science of the Gesellschaft fur ¨ Informatik (GI) in Germany, and Maison de l'Informatique et des Math e- tiques Discr etes (MIMD) in France. The conference took place in Trier { the oldest town in Germany, with more than 2 millennia of history. Previous symposia of the series were held in Paris (1984), Saarbru ¨cken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wur ¨ zburg (1993), Caen (1994), Mu ¨nchen (1995), Grenoble (1996), Lu ¨beck (1997), and Paris (1998). All proceedings of the series have been published in the Lecture Notes of Computer Science series of Springer-Verlag. STACShasbecome oneofthe mostimportantannualmeetingsin Europefor the theoretical computer science community. This time, altogether 300 authors from36countriesonv econtinentssubmittedtheirpapers.Eachsubmissionwas sent to v e members of the program committee for review. During the program committee session 51 out of the 146 submissions were accepted for presen- tion. In two of the selected papers the same result was proved independently.

Algorithms for Selfish Agentsp. 1
The Reduced Genus of a Multigraphp. 16
Classifying Discrete Temporal Propertiesp. 32
Circuit Complexity of Testing Square-Free Numbersp. 47
Relating Branching Program Size and Formula Size over the Full Binary Basisp. 57
Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machinesp. 68
The Average Time Complexity to Compute Prefix Functions in Processor Networksp. 78
On the Hardness of Permanentp. 90
One-Sided Versus Two-Sided Error in Probabilistic Computationp. 100
An Optimal Competitive Strategy for Walking in Streetsp. 110
An Optimal Strategy for Searching in Unknown Streetsp. 121
Parallel Searching on m Raysp. 132
A Logical Characterisation of Linear Time on Nondeterministic Turing Machinesp. 143
Descriptive Complexity of Computable Sequencesp. 153
Complexity of Some Problems in Universal Algebrap. 163
New Branchwidth Territoriesp. 173
Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructionsp. 184
Treewidth and Minimum Fill-In of Weakly Triangulated Graphsp. 197
Decidability and Undecidability of Marked PCPp. 207
On Quadratic Word Equationsp. 217
Some Undecidability Results Related to the Star Problem in Trace Monoidsp. 227
An Approximation Algorithm for Max p-Sectionp. 237
Approximating Bandwidth by Mixing Layouts of Interval Graphsp. 248
Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphsp. 259
Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queriesp. 270
Sparse Sets, Approximable Sets, and Parallel Queries to NPp. 281
External Selectionp. 291
Fast Computations of the Exponential Functionp. 302
A Model of Behaviour Abstraction for Communicating Processesp. 313
Model Checking Lossy Vector Addition Systemsp. 323
Constructing Light Spanning Trees with Small Routing Costp. 334
Finding Paths with the Right Costp. 345
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?p. 356
Lower Bounds for Dynamic Algebraic Problemsp. 362
An Explicit Lower Bound for TSP with Distances One and Twop. 373
Scheduling Dynamic Graphsp. 383
Supporting Increment and Decrement Operations in Balancing Networksp. 393
Worst-Case Equilibriap. 404
A Complete and Tight Average-Case Analysis of Learning Monomialsp. 414
Costs of General Purpose Learningp. 424
Universal Distributions and Time-Bounded Kolmogorov Complexityp. 434
The Descriptive Complexity Approach to LOGCFLp. 444
The Weakness of Self-Complementationp. 455
On the Difference of Horn Theoriesp. 467
On Quantum Algorithms for Noncommutative Hidden Subgroupsp. 478
On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functionsp. 488
How To Forget a Secretp. 500
A Modal Fixpoint Logic with Chopp. 510
Completeness of Neighbourhood Logicp. 521
Eliminating Recursion in the [mu]-Calculusp. 531
On Optimal Algorithms and Optimal Proof Systemsp. 541
Space Bounds for Resolutionp. 551
Upper Bounds for Vertex Cover Further Improvedp. 561
Online Matching for Scheduling Problemsp. 571
Author Indexp. 581
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540656913
ISBN-10: 354065691X
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 590
Published: 22nd February 1999
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.1
Weight (kg): 0.84