LEADER 05832nam 22007815 450 001 9910144029003321 005 20200706220613.0 010 $a3-540-45077-7 024 7 $a10.1007/b11926 035 $a(CKB)1000000000212107 035 $a(SSID)ssj0000323379 035 $a(PQKBManifestationID)11250812 035 $a(PQKBTitleCode)TC0000323379 035 $a(PQKBWorkID)10299953 035 $a(PQKB)11790607 035 $a(DE-He213)978-3-540-45077-1 035 $a(MiAaPQ)EBC3088330 035 $a(PPN)155224271 035 $a(EXLCZ)991000000000212107 100 $a20121227d2003 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aFundamentals of Computation Theory $e14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings /$fedited by Andrzej Lingas, Bengt J. Nilsson 205 $a1st ed. 2003. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2003. 215 $a1 online resource (CDLII, 440 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v2751 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-40543-7 320 $aIncludes bibliographical references at the end of each chapters and index. 327 $aApproximability 1 -- Proving Integrality Gaps without Knowing the Linear Program -- An Improved Analysis of Goemans and Williamson?s LP-Relaxation for MAX SAT -- Certifying Unsatisfiability of Random 2k-SAT Formulas Using Approximation Techniques -- Approximability 2 -- Inapproximability Results for Bounded Variants of Optimization Problems -- Approximating the Pareto Curve with Local Search for the Bicriteria TSP(1,2) Problem -- Scheduling to Minimize Max Flow Time: Offline and Online Algorithms -- Algorithms 1 -- Linear Time Algorithms for Some NP-Complete Problems on (P 5,Gem)-Free Graphs -- Graph Searching, Elimination Trees, and a Generalization of Bandwidth -- Constructing Sparse t-Spanners with Small Separators -- Composing Equipotent Teams -- Algorithms 2 -- Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers -- An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates -- Periodic Multisorting Comparator Networks -- Fast Periodic Correction Networks -- Networks and Complexity -- Games and Networks -- One-Way Communication Complexity of Symmetric Boolean Functions -- Circuits on Cylinders -- Computational Biology -- Fast Perfect Phylogeny Haplotype Inference -- On Exact and Approximation Algorithms for Distinguishing Substring Selection -- Complexity of Approximating Closest Substring Problems -- Computational Geometry -- On Lawson?s Oriented Walk in Random Delaunay Triangulations -- Competitive Exploration of Rectilinear Polygons -- An Improved Approximation Algorithm for Computing Geometric Shortest Paths -- Adaptive and Compact Discretization for Weighted Region Optimal Path Finding -- On Boundaries of Highly Visible Spaces and Applications -- Computational Models and Complexity -- Membrane Computing -- Classical Simulation Complexity of Quantum Machines -- Using Depth to Capture Average-Case Complexity -- Structural Complexity -- Non-uniform Depth of Polynomial Time and Space Simulations -- Dimension- and Time-Hierarchies for Small Time Bounds -- Baire?s Categories on Small Complexity Classes -- Formal Languages -- Operations Preserving Recognizable Languages -- Languages Defined by Generalized Equality Sets -- Context-Sensitive Equivalences for Non-interference Based Protocol Analysis -- On the Exponentiation of Languages -- Kleene?s Theorem for Weighted Tree-Automata -- Logic -- Weak Cardinality Theorems for First-Order Logic -- Compositionality of Hennessy-Milner Logic through Structural Operational Semantics -- On a Logical Approach to Estimating Computational Complexity of Potentially Intractable Problems. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v2751 606 $aComputers 606 $aAlgorithms 606 $aMathematical logic 606 $aComputer science?Mathematics 606 $aComputer graphics 606 $aTheory of Computation$3https://scigraph.springernature.com/ontologies/product-market-codes/I16005 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 606 $aComputation by Abstract Devices$3https://scigraph.springernature.com/ontologies/product-market-codes/I16013 606 $aMathematical Logic and Formal Languages$3https://scigraph.springernature.com/ontologies/product-market-codes/I16048 606 $aDiscrete Mathematics in Computer Science$3https://scigraph.springernature.com/ontologies/product-market-codes/I17028 606 $aComputer Graphics$3https://scigraph.springernature.com/ontologies/product-market-codes/I22013 615 0$aComputers. 615 0$aAlgorithms. 615 0$aMathematical logic. 615 0$aComputer science?Mathematics. 615 0$aComputer graphics. 615 14$aTheory of Computation. 615 24$aAlgorithm Analysis and Problem Complexity. 615 24$aComputation by Abstract Devices. 615 24$aMathematical Logic and Formal Languages. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aComputer Graphics. 676 $a004 702 $aLingas$b Andrzej$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aNilsson$b Bengt J$4edt$4http://id.loc.gov/vocabulary/relators/edt 712 12$aFCT 2003 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910144029003321 996 $aFundamentals of Computation Theory$92557870 997 $aUNINA