Fundamentals of Computation Theory : 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings / / edited by Andrzej Lingas, Bengt J. Nilsson

• Pubblicazione: Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003
• Edizione: 1st ed. 2003.
• Descrizione fisica: 1 online resource (CDLII, 440 p.)
• Disciplina: 004
• Soggetto topico: Computers; 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
• Persona (resp. second.): LingasAndrzej; NilssonBengt J
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di bibliografia: Includes bibliographical references at the end of each chapters and index.
• Nota di contenuto: 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.
• Titolo autorizzato: Fundamentals of Computation Theory
• ISBN: 3-540-45077-7
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910144029003321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture Notes in Computer Science, . 0302-9743 ; ; 2751