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

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.