STACS 2006
Springer Berlin (Verlag)
978-3-540-32301-3 (ISBN)
The Ubiquitous Digital Tree.- Flat Holonomies on Automata Networks.- Interprocedurally Analyzing Polynomial Identities.- External String Sorting: Faster and Cache-Oblivious.- Amortized Rigidness in Dynamic Cartesian Trees.- Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes.- On Critical Exponents in Fixed Points of Binary k-Uniform Morphisms.- Equivalence of -Algebras and Cubic Forms.- Complete Codes in a Sofic Shift.- Kolmogorov Complexity with Error.- Kolmogorov Complexity and the Recursion Theorem.- Entanglement in Interactive Proof Systems with Binary Answers.- Quantum Algorithms for Matching and Network Flows.- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound.- Estimating Entropy and Entropy Norm on Data Streams.- Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems.- Exact Price of Anarchy for Polynomial Congestion Games.- Oblivious Symmetric Alternation.- Combining Multiple Heuristics.- Conflict-Free Colorings of Rectangles Ranges.- Grid Vertex-Unfolding Orthogonal Polyhedra.- Theory and Application of Width Bounded Geometric Separator.- Invariants of Automatic Presentations and Semi-synchronous Transductions.- On the Accepting Power of 2-Tape Büchi Automata.- Weighted Picture Automata and Weighted Logics.- Markov Decision Processes with Multiple Objectives.- The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms.- Convergence and Approximation in Potential Games.- Fast FPT-Algorithms for Cleaning Grids.- Tradeoffs in Depth-Two Superconcentrators.- On Hypergraph and Graph Isomorphism with Bounded Color Classes.- Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences.- Online Learning andResource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets.- Regularity Problems for Visibly Pushdown Languages.- Regular Expressions and NFAs Without ?-Transitions.- Redundancy in Complete Sets.- Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds.- Linear Advice for Randomized Logarithmic Space.- Nested Pebbles and Transitive Closure.- Definability of Languages by Generalized First-Order Formulas over (N,+).- Generalized Modal Satisfiability.- Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games.- DAG-Width and Parity Games.- Reliable Computations Based on Locally Decodable Codes.- Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements.- A Faster Algorithm for the Steiner Tree Problem.- Generating Randomized Roundings with Cardinality Constraints and Derandomizations.- Online Sorting Buffers on Line.- Optimal Node Routing.- Memoryless Facility Location in One Pass.- Energy-Efficient Algorithms for Flow Time Minimization.- Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games.- Datalog and Constraint Satisfaction with Infinite Templates.- Evaluating Monotone Circuits on Cylinders, Planes and Tori.- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two.- Weighted Asynchronous Cellular Automata.- On the Complexity of the "Most General" Firing Squad Synchronization Problem.
| Erscheint lt. Verlag | 14.2.2006 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
| Zusatzinfo | XIX, 714 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 2250 g |
| Themenwelt | Informatik ► Software Entwicklung ► User Interfaces (HCI) |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| Schlagworte | algorithm • Algorithm analysis and problem complexity • Algorithmics • algorithms • approximation algorithms • Automat • Automata • Automata Theory • Cellular Automata • combinatorics • Complexity • Complexity theory • Computational Discrete Mathematics • Computer • Computer Science • Computer Science Logic • data structure • data structures • Distributed Systems • formal language • Formal Languages • formal methods • Game Theory • Information Theory • Kolmogorov complexity • Logic • Mathematical Logics • Parallel Computing • Programming Theory • Program Semantics • Semantics • Structural Complexity • theoretical computer science • theory of computing |
| ISBN-10 | 3-540-32301-5 / 3540323015 |
| ISBN-13 | 978-3-540-32301-3 / 9783540323013 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
