Willkommen, schön sind Sie da!
Logo Ex Libris

Fundamentals of Computation Theory

  • E-Book (pdf)
  • 440 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
This book constitutes the refereed proceedings of the 14th International Symposium Fundamentals of Computation Theory, FCT 2003, ... Weiterlesen
E-Books ganz einfach mit der kostenlosen Ex Libris-Reader-App lesen. Hiererhalten Sie Ihren Download-Link.
CHF 100.00
Download steht sofort bereit
Informationen zu E-Books
E-Books eignen sich auch für mobile Geräte (sehen Sie dazu die Anleitungen).
E-Books von Ex Libris sind mit Adobe DRM kopiergeschützt: Erfahren Sie mehr.
Weitere Informationen finden Sie hier.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

This book constitutes the refereed proceedings of the 14th International Symposium Fundamentals of Computation Theory, FCT 2003, held in Malmö, Sweden in August 2003. The 36 revised full papers presented together with an invited paper and the abstracts of 2 invited talks were carefully reviewed and selected from 73 submissions. The papers are organized in topical sections on approximibility, algorithms, networks and complexity, computational biology, computational geometry, computational models and complexity, structural complexity, formal languages, and logic.



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

Produktinformationen

Titel: Fundamentals of Computation Theory
Untertitel: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings
Editor:
EAN: 9783540450771
Format: E-Book (pdf)
Hersteller: Springer Berlin Heidelberg
Genre: IT & Internet
Veröffentlichung: 15.12.2003
Digitaler Kopierschutz: Wasserzeichen
Dateigrösse: 4.63 MB
Anzahl Seiten: 440

Weitere Bände aus der Buchreihe "Lecture Notes in Computer Science"