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

• Corporate Author: SpringerLink (Online service)
• Other Authors: Reichel, Horst (Editor, http://id.loc.gov/vocabulary/relators/edt), Tison, Sophie (Editor, http://id.loc.gov/vocabulary/relators/edt)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2000.
• Edition: 1st ed. 2000.
• Series: Lecture Notes in Computer Science, 1770
• Subjects: Data structures (Computer science).; Software engineering.; Computers.; Computer graphics.; Computer science-Mathematics.; Data Structures and Information Theory.; Software Engineering/Programming and Operating Systems.; Theory of Computation.; Computer Graphics.; Mathematics of Computing.

 Codes and Graphs -- A Classification of Symbolic Transition Systems -- Circuits versus Trees in Algebraic Complexity -- On the Many Faces of Block Codes -- A New Algorithm for MAX-2-SAT -- Bias Invariance of Small Upper Spans -- The Complexity of Planarity Testing -- About Cube-Free Morphisms -- Linear Cellular Automata with Multiple State Variables -- Two-Variable Word Equations -- Average-Case Quantum Query Complexity -- Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs -- The Boolean Hierarchy of NP-Partitions -- Binary Exponential Backoff Is Stable for High Arrival Rates -- The Data Broadcast Problem with Preemption -- An Approximate L p-Difference Algorithm for Massive Data Streams -- Succinct Representations of Model Based Belief Revision -- Logics Capturing Local Properties -- The Complexity of Poor Man's Logic -- Fast Integer Sorting in Linear Space -- On the Performance of WEAK-HEAPSORT -- On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers -- Real-Time Automata and the Kleene Algebra of Sets of Real Numbers -- Small Progress Measures for Solving Parity Games -- Multi-linearity Self-Testing with Relative Error -- Nondeterministic Instance Complexity and Hard-to-Prove Tautologies -- Hard Instances of Hard Problems -- Simulation and Bisimulation over One-Counter Processes -- Decidability of Reachability Problems for Classes of Two Counters Automata -- Hereditary History Preserving Bisimilarity Is Undecidable -- The Hardness of Approximating Spanner Problems -- An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality -- ?-Coloring of Graphs -- Optimal Proof Systems and Sparse Sets -- Almost Complete Sets -- Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results -- An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications -- Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem -- Controlled Conspiracy-2 Search -- The Stability of Saturated Linear Dynamical Systems Is Undecidable -- Tilings: Recursivity and Regularity -- Listing All Potential Maximal Cliques of a Graph -- Distance Labeling Schemes for Well-Separated Graph Classes -- Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs -- Characterizing and Deciding MSO-Definability of Macro Tree Transductions -- Languages of Dot-Depth 3/2 -- Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures -- The CNN Problem and Other k-Server Variants -- The Weighted 2-Server Problem -- On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem -- Spectral Bounds on General Hard Core Predicates -- Randomness in Visual Cryptography -- Online Dial-a-Ride Problems: Minimizing the Completion Time -- The Power Range Assignment Problem in Radio Networks on the Plane.