000 05569nam a22006015i 4500
001 978-3-540-31873-6
003 DE-He213
005 20240730194300.0
007 cr nn 008mamaa
008 100721s2005 gw | s |||| 0|eng d
020 _a9783540318736
_9978-3-540-31873-6
024 7 _a10.1007/11537311
_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 _aFundamentals of Computation Theory
_h[electronic resource] :
_b15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings /
_cedited by Maciej Liskiewicz, Rüdiger Reischuk.
250 _a1st ed. 2005.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2005.
300 _aXVI, 580 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 ;
_v3623
505 0 _aInvited Talks -- The Complexity of Querying External Memory and Streaming Data -- The Smoothed Analysis of Algorithms -- Path Coupling Using Stopping Times -- Circuits -- On the Incompressibility of Monotone DNFs -- Bounds on the Power of Constant-Depth Quantum Circuits -- Automata I -- Biautomatic Semigroups -- Deterministic Automata on Unranked Trees -- Complexity I -- Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals -- Generic Density and Small Span Theorem -- Approximability -- Logspace Optimization Problems and Their Approximability Properties -- A Faster and Simpler 2-Approximation Algorithm for Block Sorting -- Computational and Structural Complexity -- On the Power of Unambiguity in Alternating Machines -- Translational Lemmas for Alternating TMs and PRAMs -- Collapsing Recursive Oracles for Relativized Polynomial Hierarchies -- Graphs and Complexity -- Exact Algorithms for Graph Homomorphisms -- Improved Algorithms and Complexity Results for Power Domination in Graphs -- Clique-Width for Four-Vertex Forbidden Subgraphs -- Computational Game Theory -- On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems -- Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems -- Visual Cryptography and Computational Geometry -- Perfect Reconstruction of Black Pixels Revisited -- Adaptive Zooming in Point Set Labeling -- Query Complexity -- On the Black-Box Complexity of Sperner's Lemma -- Property Testing and the Branching Program Size of Boolean Functions -- Distributed Systems -- Almost Optimal Explicit Selectors -- The Delayed k-Server Problem -- Automata and Formal Languages -- Leftist Grammars and the Chomsky Hierarchy -- Shrinking Multi-pushdown Automata -- Graph Algorithms -- A Simple and Fast Min-cut Algorithm.-(Non)-Approximability for the Multi-criteria TSP(1,2) -- Semantics -- Completeness and Compactness of Quantitative Domains -- A Self-dependency Constraint in the Simply Typed Lambda Calculus -- A Type System for Computationally Secure Information Flow -- Approximation Algorithms -- Algorithms for Graphs Embeddable with Few Crossings Per Edge -- Approximation Results for the Weighted P 4 Partition Problems -- The Maximum Resource Bin Packing Problem -- Average-Case Complexity -- Average-Case Non-approximability of Optimisation Problems -- Relations Between Average-Case and Worst-Case Complexity -- Algorithms -- Reconstructing Many Partitions Using Spectral Techniques -- Constant Time Generation of Linear Extensions -- Complexity II -- On Approximating Real-World Halting Problems -- An Explicit Solution to Post's Problem over the Reals -- The Complexity of Semilinear Problems in Succinct Representation -- Graph Algorithms -- On Finding Acyclic Subhypergraphs -- An Improved Approximation Algorithm for TSP with Distances One and Two -- New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem -- Automata II -- On the Expressiveness of Asynchronous Cellular Automata -- Tree Automata and Discrete Distributed Games -- Pattern Matching -- A New Linearizing Restriction in the Pattern Matching Problem -- Fully Incremental LCS Computation.
650 0 _aComputer science.
_99832
650 0 _aAlgorithms.
_93390
650 0 _aMachine theory.
_9156455
650 0 _aComputer science
_xMathematics.
_93866
650 0 _aDiscrete mathematics.
_912873
650 0 _aComputer graphics.
_94088
650 1 4 _aTheory of Computation.
_9156456
650 2 4 _aAlgorithms.
_93390
650 2 4 _aFormal Languages and Automata Theory.
_9156457
650 2 4 _aDiscrete Mathematics in Computer Science.
_931837
650 2 4 _aComputer Graphics.
_94088
700 1 _aLiskiewicz, Maciej.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9156458
700 1 _aReischuk, Rüdiger.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9156459
710 2 _aSpringerLink (Online service)
_9156460
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540281931
776 0 8 _iPrinted edition:
_z9783540814016
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v3623
_9156461
856 4 0 _uhttps://doi.org/10.1007/11537311
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c95119
_d95119