000 05089nam a22005655i 4500
001 978-3-540-46541-6
003 DE-He213
005 20160624102015.0
007 cr nn 008mamaa
008 121227s2000 gw | s |||| 0|eng d
020 _a9783540465416
_9978-3-540-46541-6
024 7 _a10.1007/3-540-46541-3
_2doi
050 4 _aQA75.5-76.95
072 7 _aUY
_2bicssc
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aCOM031000
_2bisacsh
082 0 4 _a004.0151
_223
245 1 0 _aSTACS 2000
_h[electronic resource] :
_b17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17–19, 2000 Proceedings /
_cedited by Horst Reichel, Sophie Tison.
260 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2000.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2000.
300 _aXIV, 670 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v1770
505 0 _aCodes 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.
650 0 _aComputer science.
650 0 _aSoftware engineering.
650 0 _aData structures (Computer science).
650 0 _aInformation theory.
650 0 _aComputer graphics.
650 1 4 _aComputer Science.
650 2 4 _aTheory of Computation.
650 2 4 _aSoftware Engineering/Programming and Operating Systems.
650 2 4 _aData Structures, Cryptology and Information Theory.
650 2 4 _aComputer Graphics.
650 2 4 _aMathematics of Computing.
700 1 _aReichel, Horst.
_eeditor.
700 1 _aTison, Sophie.
_eeditor.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783540671411
786 _dSpringer
830 0 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v1770
856 4 0 _uhttp://dx.doi.org/10.1007/3-540-46541-3
942 _2EBK5817
_cEBK
999 _c35111
_d35111