+612 9045 4394
$7.95 Delivery per order to Australia and New Zealand
100% Australian owned
Over a hundred thousand in-stock titles ready to ship
STACS 2000 : 17th Annual Symposium on Theortical Aspects of Computer Science, Lille, France, February 17-19, 2000, Proceedings :  17th Annual Symposium on Theortical Aspects of Computer Science, Lille, France, February 17-19, 2000, Proceedings - Horst Reichel

STACS 2000 : 17th Annual Symposium on Theortical Aspects of Computer Science, Lille, France, February 17-19, 2000, Proceedings

17th Annual Symposium on Theortical Aspects of Computer Science, Lille, France, February 17-19, 2000, Proceedings

By: Horst Reichel (Editor), Sophie Tison (Editor)

Paperback Published: March 2000
ISBN: 9783540671411
Number Of Pages: 670

Share This Book:


or 4 easy payments of $51.04 with Learn more
Ships in 10 to 15 business days

Earn 408 Qantas Points
on this Book

This book constitutes the refereed proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, held in Lille, France in February 2000.The 51 revised full papers presented together with the three invited papers were carefully reviewed and selected from a total of 146 submissions on the basis of some 700 reviewers' reports. The papers address fundamental issues from all current areas of theoretical computer science including algorithms, data structures, automata, formal languages, complexity, verification, logic, cryptography, graph theory, optimization, etc.

Codes and Graphsp. 1
A Classification of Symbolic Transition Systemsp. 13
Circuits versus Trees in Algebraic Complexityp. 35
On the Many Faces of Block Codesp. 53
A New Algorithm for MAX-2-SATp. 65
Bias Invariance of Small Upper Spansp. 74
The Complexity of Planarity Testingp. 87
About Cube-Free Morphismsp. 99
Linear Cellular Automata with Multiple State Variablesp. 110
Two-Variable Word Equationsp. 122
Average-Case Quantum Query Complexityp. 133
Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programsp. 145
The Boolean Hierarchy of NP-Partitionsp. 157
Binary Exponential Backoff Is Stable for High Arrival Ratesp. 169
The Data Broadcast Problem with Preemptionp. 181
An Approximate Lp-Difference Algorithm for Massive Data Streamsp. 193
Succinct Representations of Model Based Belief Revisionp. 205
Logics Capturing Local Propertiesp. 217
The Complexity of Poor Man's Logicp. 230
Fast Integer Sorting in Linear Spacep. 242
On the Performance of WEAK-HEAPSORTp. 254
On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbersp. 267
Real-Time Automata and the Kleene Algebra of Sets of Real Numbers.p. 279
Small Progress Measures for Solving Parity Gamesp. 290
Multi-linearity Self-Testing with Relative Errorp. 302
Nondeterministic Instance Complexity and Hard-to-Prove Tautologiesp. 314
Hard Instances of Hard Problemsp. 324
Simulation and Bisimulation over One-Counter Processesp. 334
Decidability of Reachability Problems for Classes of Two Counters Automatap. 346
Hereditary History Preserving Bisimilarity Is Undecidablep. 358
The Hardness of Approximating Spanner Problemsp. 370
An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequalityp. 382
¿-Coloring of Graphsp. 395
Optimal Proof Systems and Sparse Setsp. 407
Almost Complete Setsp. 419
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Resultsp. 431
An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communicationsp. 443
Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problemp. 455
Controlled Conspiracy-2 Searchp. 466
The Stability of Saturated Linear Dynamical Systems Is Undecidablep. 479
Tilings: Recursivity and Regularityp. 491
Listing All Potential Maximal Cliques of a Graphp. 503
Distance Labeling Schemes for Well-Separated Graph Classesp. 516
Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphsp. 529
Characterizing and Deciding MSO-Definability of Macro Tree Transductionsp. 542
Languages of Dot-Depth 3/2p. 555
Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structuresp. 567
The CNN Problem and Other fc-Server Variantsp. 581
The Weighted 2-Server Problemp. 593
On the Competitive Ratio of the Work Function Algorithm for the k-Server Problemp. 605
Spectral Bounds on General Hard Core Predicatesp. 614
Randomness in Visual Cryptographyp. 626
Online Dial-a-Ride Problems: Minimizing the Completion Timep. 639
The Power Range Assignment Problem in Radio Networks on the Planep. 651
Author Indexp. 661
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9783540671411
ISBN-10: 3540671412
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 670
Published: March 2000
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.48
Weight (kg): 0.94

Earn 408 Qantas Points
on this Book