STACS 2000
Springer Berlin (Verlag)
978-3-540-67141-1 (ISBN)
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.- GraphIsomorphism 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.
| Erscheint lt. Verlag | 9.2.2000 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | XIV, 670 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 872 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Schlagworte | algorithms • Automat • Automata • Automata Theory • Complexity • Computer • Computer Science • data structures • Discrete Mathematics • formal language • Formal Languages • Informatik • Logic • Logical Foundations • Optimization • Programming Theory • theoretical computer science • theory of computing • verification |
| ISBN-10 | 3-540-67141-2 / 3540671412 |
| ISBN-13 | 978-3-540-67141-1 / 9783540671411 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
