Format:
Online-Ressource
ISBN:
9783540465416
,
3540465413
Series Statement:
Lecture Notes in Computer Science 1770
Content:
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.
Note:
Includes bibliographical references and index
,
""Lecture Notes in Computer Science""; ""STACS 2000""; ""Preface""; ""Program Committee""; ""Table of Contents""; ""Codes and Graphs""; ""Introduction""; ""Channels and Codes""; ""LDPC Codes""; ""Code Construction""; ""Decoding on the Erasure Channel""; ""The Analysis""; ""Capacity Achieving Sequences""; ""Codes on Other Channels""; ""Conclusion and Open Problems""; ""A Classification of Symbolic Transition Systems?""; ""Introduction""; ""Symbolic Transition Systems""; ""Example: Polyhedral Hybrid Automata""; ""Background Definitions""; ""Preview""; ""Class-1 Symbolic Transition Systems""
,
""Finite Characterization: Bisimilarity""""Symbolic State-Space Exploration: Partition Refinement""; ""Decidable Properties: Branching Time""; ""Example: Singular Hybrid Automata""; ""Class-2 Symbolic Transition Systems""; ""Finite Characterization: Similarity""; ""Symbolic State-Space Exploration: Intersection Refinement""; ""Decidable Properties: Negation-Free Branching Time""; ""Example: 2D Rectangular Hybrid Automata""; ""Class-3 Symbolic Transition Systems""; ""Finite Characterization: Traces""; ""Symbolic State-Space Exploration: Observation Refinement""
,
""Decidable Properties: Linear Time""""Example: Rectangular Hybrid Automata""; ""Class-4 Symbolic Transition Systems""; ""Finite Characterization: Equi-distant Targets""; ""Symbolic State-Space Exploration: Predecessor Iteration""; ""Decidable Properties: Conjunction-Free Linear Time""; ""Class-5 Symbolic Transition Systems""; ""Finite Characterization: Bounded-Distance Targets""; ""Symbolic State-Space Exploration: Predecessor Aggregation""; ""Decidable Properties: Bounded Reachability""; ""Example: Networks of Rectangular Hybrid Automata""; ""General Symbolic Transition Systems""
,
""Circuits versus Trees in Algebraic Complexity""""Introduction""; ""Computation Models""; ""Arbitrary Structures""; ""Trees""; ""Circuits""; ""Complexity Classes""; ""Is P Equal to NP ?""; ""Complexity and Point Location""; ""Point Location by Computation Trees""; ""Branching Complexity of Point Location""; ""The Computation Tree Alternative""; ""On the Many Faces of Block Codes""; ""Introduction""; ""Background""; ""Overlaying of Subtrellises""; ""Decoding""; ""The Viterbi Decoding Algorithm""; ""The A^{*} Algorithm""; ""Decoding on an Overlayed Trellis""; ""Conclusions""
,
""A New Algorithm for MAX-2-SAT?""""Introduction""; ""Background""; ""Results""; ""Conclusion""; ""Acknowledgement""; ""Bias Invariance of Small Upper Spans (Extended Abstract)?""; ""Introduction""; ""Preliminaries""; ""Resource-Bounded nu -Measure""; ""Truth-Table Reductions""; ""Martingale Contraction""; ""Bias Invariance""; ""The Complexity of Planarity Testing""; ""Introduction""; ""Hardness of Planarity Testing""; ""The unhbox voidb x hbox {{sf SL}} Algorithm for Planarity Testing and Embedding""; ""Elementary Graph Computations in unhbox voidb @x hbox {{sf SL}}""
,
""Finding an Open Ear Decomposition""
Additional Edition:
ISBN 9783540671411
Additional Edition:
Buchausg. u.d.T. STACS (17 : 2000 : Lille) STACS 2000 Berlin : Springer, 2000 ISBN 3540671412
Language:
English
Keywords:
Theoretische Informatik
;
Theoretische Informatik
;
Konferenzschrift
DOI:
10.1007/3-540-46541-3
URL:
Volltext
(lizenzpflichtig)
URL:
Volltext
(lizenzpflichtig)
