000 06026nam a22005775i 4500
001 978-3-540-31856-9
003 DE-He213
005 20240730182024.0
007 cr nn 008mamaa
008 100302s2005 gw | s |||| 0|eng d
020 _a9783540318569
_9978-3-540-31856-9
024 7 _a10.1007/b106485
_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 2005
_h[electronic resource] :
_b22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2004, Proceedings /
_cedited by Volker Diekert, Bruno Durand.
250 _a1st ed. 2005.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2005.
300 _aXVI, 706 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v3404
505 0 _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, MaximalConstraint 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 -- PatternOccurrences in Multicomponent Models -- Automatic Presentations for Finitely Generated Groups.
650 0 _aComputer science.
_99832
650 0 _aArtificial intelligence
_xData processing.
_921787
650 0 _aComputer science
_xMathematics.
_93866
650 0 _aDiscrete mathematics.
_912873
650 0 _aComputer graphics.
_94088
650 1 4 _aTheory of Computation.
_9126981
650 2 4 _aData Science.
_934092
650 2 4 _aDiscrete Mathematics in Computer Science.
_931837
650 2 4 _aComputer Graphics.
_94088
700 1 _aDiekert, Volker.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9126982
700 1 _aDurand, Bruno.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9126983
710 2 _aSpringerLink (Online service)
_9126984
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540249986
776 0 8 _iPrinted edition:
_z9783540807919
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v3404
_9126985
856 4 0 _uhttps://doi.org/10.1007/b106485
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c91190
_d91190