STACS 2005 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2004, Proceedings

Bibliographic Details
Other Authors: Diekert, Volker (Editor), Durand, Bruno (Editor)
Format: eBook
Language:English
Published: Berlin, Heidelberg Springer Berlin Heidelberg 2005, 2005
Edition:1st ed. 2005
Series:Theoretical Computer Science and General Issues
Subjects:
Online Access:
Collection: Springer eBooks 2005- - Collection details see MPG.ReNa
LEADER 05150nmm a2200397 u 4500
001 EB000375072
003 EBX01000000000000000228124
005 00000000000000.0
007 cr|||||||||||||||||||||
008 130626 ||| eng
020 |a 9783540318569 
100 1 |a Diekert, Volker  |e [editor] 
245 0 0 |a STACS 2005  |h Elektronische Ressource  |b 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2004, Proceedings  |c edited by Volker Diekert, Bruno Durand 
250 |a 1st ed. 2005 
260 |a Berlin, Heidelberg  |b Springer Berlin Heidelberg  |c 2005, 2005 
300 |a XVI, 706 p  |b online resource 
505 0 |a Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations -- Session 5B -- Connectivity for Wireless Agents Moving on a Cycle or Grid -- Improved Algorithms for Dynamic Page Migration -- Approximate Range Mode and Range Median Queries -- Session 6A -- Topological Automata -- Minimizing NFA’s and Regular Expressions -- Session 6B -- Increasing Kolmogorov Complexity -- Kolmogorov-Loveland Randomness and Stochasticity -- Session 7A -- Information Theory in Property Testing and Monotonicity Testing in Higher Dimension -- On Nash Equilibria in Non-cooperative All-Optical Networks -- Speed Scaling to Manage Temperature -- Session 7B -- The Complexity of Solving Linear Equations over a Finite Ring -- A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields -- Characterizing TC0 in Terms of Infinite Groups -- Session 8A -- Fast Pruning of Geometric Spanners -- The PIGs Full Monty – A Floor Show of Minimal Separators --  
505 0 |a Centrality Measures Based on Current Flow -- Session 8B -- Varieties of Codes and Kraft Inequality -- Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes -- The Power of Commuting with Finite Sets of Words -- Session 9A -- Exact Quantum Algorithms for the Leader Election Problem -- Robust Polynomials and Quantum Algorithms -- Quantum Interactive Proofs with Competing Provers -- Session 9B -- Roundings Respecting Hard Constraints -- Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves -- Cycle Cover with Short Cycles -- Session 10A -- A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs -- All-Pairs Nearly 2-Approximate Shortest-Paths in O(n 2 polylog n) Time -- Session 10B -- PatternOccurrences in Multicomponent Models -- Automatic Presentations for Finitely Generated Groups 
505 0 |a Polylog-Time Reductions Decrease Dot-Depth -- On the Computational Complexity of the Forcing Chromatic Number -- More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP -- Session 3B -- Three Optimal Algorithms for Balls of Three Colors -- Cost Sharing and Strategyproof Mechanisms for Set Cover Games -- On Weighted Balls-into-Bins Games -- Session 4A -- Computing Minimal Multi-homogeneous Bézout Numbers Is Hard -- Dynamic Complexity Theory Revisited -- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size -- Session 4B -- Shortest Monotone Descent Path Problem in Polyhedral Terrain -- Packet Buffering: Randomization Beats Deterministic Algorithms -- Solving Medium-Density Subset Sum Problems in Expected Polynomial Time -- Session 5A -- Quantified Constraint Satisfaction, MaximalConstraint Languages, and Symmetric Polymorphisms -- Regular Tree Languages Definable in FO --  
505 0 |a Invited Talks -- Automorphisms of Finite Rings and Applications to Complexity of Problems -- Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages -- Algorithmics in Exponential Time -- Session 1A -- Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics -- Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms -- Truthful Approximation Mechanisms for Scheduling Selfish Related Machines -- Session 1B -- Counting in the Two Variable Guarded Logic with Transitivity -- The Variable Hierarchy of the ?-Calculus Is Strict -- The Core of a Countably Categorical Structure -- Session 2A -- How Common Can Be Universality for Cellular Automata? -- Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods -- Session 2B -- On the Decidability of Temporal Properties of Probabilistic Pushdown Automata -- Deciding Properties of Contract-Signing Protocols -- Session 3A --  
653 |a Artificial intelligence / Data processing 
653 |a Computer graphics 
653 |a Computer science 
653 |a Computer science / Mathematics 
653 |a Discrete Mathematics in Computer Science 
653 |a Computer Graphics 
653 |a Discrete mathematics 
653 |a Theory of Computation 
653 |a Data Science 
700 1 |a Durand, Bruno  |e [editor] 
041 0 7 |a eng  |2 ISO 639-2 
989 |b Springer  |a Springer eBooks 2005- 
490 0 |a Theoretical Computer Science and General Issues 
028 5 0 |a 10.1007/b106485 
856 4 0 |u https://doi.org/10.1007/b106485?nosfx=y  |x Verlag  |3 Volltext 
082 0 |a 004.0151