STACS 2004 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004. Proceedings /

• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Άλλοι συγγραφείς: Diekert, Volker (Επιμελητής έκδοσης), Habib, Michel (Επιμελητής έκδοσης)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg, 2004.
• Σειρά: Lecture Notes in Computer Science, 2996
• Θέματα: Computer science.; Data structures (Computer science).; Computers.; Algorithms.; Computer logic.; Mathematical logic.; Computer Science.; Theory of Computation.; Computation by Abstract Devices.; Data Structures.; Algorithm Analysis and Problem Complexity.; Logics and Meanings of Programs.; Mathematical Logic and Formal Languages.

 Invited 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 Problems Complete 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 Related Machines -- 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.