05856nam 22007815 450 99646596960331620200706220613.03-540-45077-710.1007/b11926(CKB)1000000000212107(SSID)ssj0000323379(PQKBManifestationID)11250812(PQKBTitleCode)TC0000323379(PQKBWorkID)10299953(PQKB)11790607(DE-He213)978-3-540-45077-1(MiAaPQ)EBC3088330(PPN)155224271(EXLCZ)99100000000021210720121227d2003 u| 0engurnn|008mamaatxtccrFundamentals of Computation Theory[electronic resource] 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings /edited by Andrzej Lingas, Bengt J. Nilsson1st ed. 2003.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,2003.1 online resource (CDLII, 440 p.) Lecture Notes in Computer Science,0302-9743 ;2751Bibliographic Level Mode of Issuance: Monograph3-540-40543-7 Includes bibliographical references at the end of each chapters and index.Approximability 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.Lecture Notes in Computer Science,0302-9743 ;2751ComputersAlgorithmsMathematical logicComputer science—MathematicsComputer graphicsTheory of Computationhttps://scigraph.springernature.com/ontologies/product-market-codes/I16005Algorithm Analysis and Problem Complexityhttps://scigraph.springernature.com/ontologies/product-market-codes/I16021Computation by Abstract Deviceshttps://scigraph.springernature.com/ontologies/product-market-codes/I16013Mathematical Logic and Formal Languageshttps://scigraph.springernature.com/ontologies/product-market-codes/I16048Discrete Mathematics in Computer Sciencehttps://scigraph.springernature.com/ontologies/product-market-codes/I17028Computer Graphicshttps://scigraph.springernature.com/ontologies/product-market-codes/I22013Computers.Algorithms.Mathematical logic.Computer science—Mathematics.Computer graphics.Theory of Computation.Algorithm Analysis and Problem Complexity.Computation by Abstract Devices.Mathematical Logic and Formal Languages.Discrete Mathematics in Computer Science.Computer Graphics.004Lingas Andrzejedthttp://id.loc.gov/vocabulary/relators/edtNilsson Bengt Jedthttp://id.loc.gov/vocabulary/relators/edtFCT 2003 MiAaPQMiAaPQMiAaPQBOOK996465969603316Fundamentals of computation theory382778UNISA