LEADER 05639nam 2200553 a 450 001 9910484929903321 005 20200520144314.0 024 7 $a10.1007/b106485 035 $a(CKB)1000000000212853 035 $a(SSID)ssj0000320183 035 $a(PQKBManifestationID)11263716 035 $a(PQKBTitleCode)TC0000320183 035 $a(PQKBWorkID)10360926 035 $a(PQKB)11781499 035 $a(DE-He213)978-3-540-31856-9 035 $a(MiAaPQ)EBC3067521 035 $a(PPN)123092248 035 $a(EXLCZ)991000000000212853 100 $a20050113d2005 uy 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aSTACS 2005 $e22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005 : proceedings /$fVolker Diekert, Bruno Durand (eds.) 205 $a1st ed. 2005. 210 $aBerlin ;$aNew York $cSpringer$dc2005 215 $a1 online resource (XVI, 706 p.) 225 1 $aLecture notes in computer science,$x0302-9743 ;$v3404 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$aPrinted edition: 9783540249986 320 $aIncludes bibliographical references and index. 327 $aInvited 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 -- 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, Maximal Constraint Languages, and Symmetric Polymorphisms -- Regular Tree Languages Definable in FO -- 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 -- 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 -- Pattern Occurrences in Multicomponent Models -- Automatic Presentations for Finitely Generated Groups. 410 0$aLecture notes in computer science ;$v3404. 517 3 $a22nd Annual Symposium on Theoretical Aspects of Computer Science 517 3 $aSymposium on Theoretical Aspects of Computer Science 517 3 $aTheoretical aspects of computer science 606 $aComputer science$vCongresses 615 0$aComputer science 676 $a004 701 $aDiekert$b Volker$f1955-$01220869 701 $aDurand$b B$g(Bruno)$01753878 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484929903321 996 $aSTACS 2005$94189940 997 $aUNINA