000 06188nam a22005895i 4500
001 978-3-540-24749-4
003 DE-He213
005 20240423130118.0
007 cr nn 008mamaa
008 121227s2004 gw | s |||| 0|eng d
020 _a9783540247494
_9978-3-540-24749-4
024 7 _a10.1007/b96012
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
245 1 0 _aSTACS 2004
_h[electronic resource] :
_b21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings /
_cedited by Volker Diekert, Michel Habib.
250 _a1st ed. 2004.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2004.
300 _aXVI, 660 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,
_x1611-3349 ;
_v2996
505 0 _aInvited Lectures -- Approximation Schemes for Metric Clustering Problems -- Positional Determinacy of Infinite Games -- Structural Complexity (I) -- Individual Communication Complexity -- The Complexity of Satisfiability Problems over Finite Lattices -- Constant Width Planar Computation Characterizes ACC0 -- Graph Algorithms (I) -- A Simple and Fast Approach for Solving Problems on Planar Graphs -- Sum-Multicoloring on Paths -- Matching Algorithms Are Fast in Sparse Random Graphs -- Quantum Computations -- Algebraic Results on Quantum Automata -- Quantum Identification of Boolean Oracles -- Pattern Inference and Statistics -- Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models -- A Discontinuity in Pattern Inference -- Satisfiability – Constraint Satisfaction Problem -- Algorithms for SAT Based on Search in Hamming Balls -- Identifying Efficiently Solvable Cases of Max CSP -- The Complexity of Boolean Constraint Isomorphism -- Scheduling (I) -- On Minimizing the Total Weighted Tardiness on a Single Machine -- Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs -- Optimal and Online Preemptive Scheduling on Uniformly Related Machines -- Algorithms -- Parallel Prefetching and Caching Is Hard -- Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem -- Approximation Algorithms for Minimizing Average Distortion -- Networks (I) -- Digraphs Exploration with Little Memory -- Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks -- An Algorithmic View on OVSF Code Assignment -- Automata Theory and Words -- The Syntactic Graph of a Sofic Shift -- Periodicity and Unbordered Words -- Desert Automata and the Finite Substitution Problem -- Structural Complexity (II) -- Satisfiability ProblemsComplete for Deterministic Logarithmic Space -- A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number -- The Minimal Logically-Defined NP-Complete Problem -- Path Algorithms -- Solving the 2-Disjoint Paths Problem in Nearly Linear Time -- Simpler Computation of Single-Source Shortest Paths in Linear Average Time -- Cryptography -- Lattices with Many Cycles Are Dense -- Automata-Based Analysis of Recursive Cryptographic Protocols -- Networks (II) -- On Minimum Circular Arrangement -- Integral Symmetric 2-Commodity Flows -- Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks -- Logic and Formal Languages -- On the Expressiveness of Deterministic Transducers over Infinite Trees -- Definability and Regularity in Automatic Structures -- Active Context-Free Games -- Graphs Algorithms (II) -- Worst Case Performance of an Approximation Algorithm for Asymmetric TSP -- On Visibility Representation of Plane Graphs -- Topology Matters: Smoothed Competitiveness of Metrical Task Systems -- Game Theory and Complexity -- A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees -- The Plurality Problem with Three Colors -- A Measured Collapse of the Modal ?-Calculus Alternation Hierarchy -- Networks (III) -- An Information Theoretic Lower Bound for Broadcasting in Radio Networks -- A New Model for Selfish Routing -- Broadcast in the Rendezvous Model -- Structural Complexity (III) -- Time-Space Tradeoff in Derandomizing Probabilistic Logspace -- What Can be Efficiently Reduced to the K-Random Strings? -- Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms -- Scheduling (II) -- Deterministic Truthful Approximation Mechanisms for Scheduling RelatedMachines -- The Expected Competitive Ratio for Weighted Completion Time Scheduling -- Algorithmic Information -- Effective Strong Dimension in Algorithmic Information and Computational Complexity -- A Lower Bound on the Competitive Ratio of Truthful Auctions -- Errata to STACS 2003 -- Errata to Analysis of the Harmonic Algorithm for Three Servers.
650 0 _aComputer science.
650 0 _aArtificial intelligence
_xData processing.
650 0 _aAlgorithms.
650 0 _aMachine theory.
650 1 4 _aTheory of Computation.
650 2 4 _aData Science.
650 2 4 _aAlgorithms.
650 2 4 _aComputer Science Logic and Foundations of Programming.
650 2 4 _aFormal Languages and Automata Theory.
700 1 _aDiekert, Volker.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aHabib, Michel.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540212362
776 0 8 _iPrinted edition:
_z9783662209097
830 0 _aLecture Notes in Computer Science,
_x1611-3349 ;
_v2996
856 4 0 _uhttps://doi.org/10.1007/b96012
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
912 _aZDB-2-BAE
942 _cSPRINGER
999 _c185170
_d185170