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

Λεπτομέρειες βιβλιογραφικής εγγραφής
Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
Άλλοι συγγραφείς: Reichel, Horst (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt), Tison, Sophie (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt)
Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
Γλώσσα:English
Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2000.
Έκδοση:1st ed. 2000.
Σειρά:Lecture Notes in Computer Science, 1770
Θέματα:
Διαθέσιμο Online:Full Text via HEAL-Link
Πίνακας περιεχομένων:
  • 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.