Fundamentals of Computation Theory

The papers in this volume were presented at the 14th Symposium on Fun- mentals of Computation Theory. The symposium was established in 1977 as a biennial event for researchers interested in all aspects of theoretical computer science, in particular in al- rithms, complexity, and formal and logical methods. The previous FCT con- rences were held in the following cities: Poznan (Poland, 1977), Wendisch-Rietz (Germany, 1979), Szeged (Hungary, 1981), Borgholm (Sweden, 1983), Cottbus (Germany, 1985), Kazan (Russia, 1987), Szeged (Hungary, 1989), Gosen-Berlin (Germany, 1991), Szeged (Hungary, 1993), Dresden (Germany, 1995), Krak ow (Poland, 1997), Iasi (Romania, 1999), and Riga (Latvia, 2001). The FCT conferences are coordinated by the FCT steering committee, which consistsofB.Chlebus(Denver/Warsaw),Z.Esik(Szeged),M.Karpinski(Bonn), A. Lingas (Lund), M. Santha (Paris), E. Upfal (Providence), and I. Wegener (Dortmund). The call for papers sought contributions on original research in all aspects of theoretical computer science including design and analysis of algorithms, abstract data types, approximation algorithms, automata and formal lang- ges, categorical and topological approaches, circuits, computational and str- turalcomplexity,circuitandprooftheory,computationalbiology,computational geometry, computer systems theory, concurrency theory, cryptography, domain theory, distributed algorithms and computation, molecular computation, qu- tum computation and information, granular computation, probabilistic com- tation, learning theory, rewriting, semantics, logicin computer science, speci?- tion, transformation and veri?cation, and algebraic aspects of computer science. There were 73 papers submitted, of which the majority were very good.

Inhalt
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 SimulationComplexity 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.