Fundamentals of Computation Theory: 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, ProceedingsThis volume is dedicated to the 15th Symposium on Fundamentals of Com- tation Theory FCT 2005, held in Lu ]beck, Germany, on August 17-20, 2005. The FCT symposium was established in 1977 as a biennial event for - searchers interested in all aspects of theoretical computer science, in particular in algorithms, complexity, and formal and logical methods. The previous FCT conferences were held in the following places: 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), Riga (Latvia, 2001) and Malmo ] (Sweden, 2003). The FCT conference seriesis coordinatedby a steering comm- tee. Its current members are B. 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 for FCT 2005 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 languages, categorical and topological approaches, circuits, computational and structural complexity, circuit and proof theory, computational biology, com- tational geometry, computer systems theory, concurrency theory, cryptography, domain theory, distributed algorithms and computation, molecular computation, quantumcomputation and information, granular computation, probabilistic c- putation, learning theory, rewriting, semantics, logic in computer science, spe- ?cation, transformation and veri?cation, and algebraic aspects of computer s- ence. |
What people are saying - Write a review
We haven't found any reviews in the usual places.
Contents
The Complexity of Querying External Memory and Streaming Data | 1 |
The Smoothed Analysis of Algorithms | 17 |
Path Coupling Using Stopping Times | 19 |
On the Incompressibility of Monotone DNFs | 32 |
Bounds on the Power of ConstantDepth Quantum Circuits | 44 |
Biautomatic Semigroups | 56 |
Deterministic Automata on Unranked Trees | 68 |
Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals | 80 |
Shrinking Multipushdown Automata | 305 |
A Simple and Fast Mincut Algorithm | 317 |
TSP12 | 329 |
Completeness and Compactness of Quantitative Domains | 341 |
A Selfdependency Constraint in the Simply Typed Lambda Calculus | 352 |
A Type System for Computationally Secure Information Flow | 365 |
Algorithms for Graphs Embeddable with Few Crossings Per Edge | 378 |
Approximation Results for the Weighted P4 Partition Problems | 388 |
Generic Density and Small Span Theorem | 92 |
Logspace Optimization Problems and Their Approximability Properties | 103 |
A Faster and Simpler 2Approximation Algorithm for Block Sorting | 115 |
On the Power of Unambiguity in Alternating Machines | 125 |
Translational Lemmas for Alternating TMs and PRAMs | 137 |
Collapsing Recursive Oracles for Relativized Polynomial Hierarchies | 149 |
Exact Algorithms for Graph Homomorphisms | 161 |
Improved Algorithms and Complexity Results for Power Domination in Graphs | 172 |
CliqueWidth for FourVertex Forbidden Subgraphs | 185 |
On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems | 197 |
Simple Stochastic Games and PMatrix Generalized Linear Complementarity Problems | 209 |
Perfect Reconstruction of Black Pixels Revisited | 221 |
Adaptive Zooming in Point Set Labeling | 233 |
On the BlackBox Complexity of Sperners Lemma | 245 |
Property Testing and the Branching Program Size of Boolean Functions | 258 |
Almost Optimal Explicit Selectors | 270 |
The Delayed kServer Problem | 281 |
Leftist Grammars and the Chomsky Hierarchy | 293 |
The Maximum Resource Bin Packing Problem | 397 |
AverageCase Nonapproximability of Optimisation Problems | 409 |
Relations Between AverageCase and WorstCase Complexity | 422 |
Reconstructing Many Partitions Using Spectral Techniques | 433 |
Constant Time Generation of Linear Extensions | 445 |
On Approximating RealWorld Halting Problems | 454 |
An Explicit Solution to Posts Problem over the Reals | 467 |
The Complexity of Semilinear Problems in Succinct Representation | 479 |
On Finding Acyclic Subhypergraph | 491 |
An Improved Approximation Algorithm for TSP with Distances One and Two | 504 |
New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem | 516 |
Automata | 528 |
Tree Automata and Discrete Distributed Games | 540 |
A New Linearizing Restriction in the Pattern Matching Problem | 552 |
Fully Incremental LCS Computation | 563 |
| 575 | |
Other editions - View all
Fundamentals of Computation Theory: 15th International Symposium, FCT 2005 ... Maciej Liskiewicz No preview available - 2005 |
Common terms and phrases
abs-block approximation algorithm automata automaton Berlin Heidelberg 2005 biautomatic boolean c-nodes circuit clique clique-width complexity classes Computer Science consider constant construct contains Corollary corresponding define defined Definition deletion denote deterministic DistNP distributed dominating edge equivalent exists finite first function gates given graph G Halting problem hierarchy homomorphism hyperedges hypergraph independent sets induced subgraph input integer k-server problem labels language least leftmost Lemma linear extension Liskiewicz LNCS lower bound matching substrings matrix node notion NP-complete obtain optimal oracle output P-matrix paper partition point path polynomial polynomial hierarchy polynomial-time Proc Proof properties Proposition prove PSPACE quantum quantum circuit qubits query query complexity random ratio recursive Reischuk Eds restriction Section semigroup sequence solution string structure subgraph subset symbol tape Theorem Theory tree treewidth Turing machine undirected graph variables vertex vertices
Bibliographic information
| Title | Fundamentals of Computation Theory: 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings Volume 3623 of LNCS sublibrary: Theoretical computer science and general issues Volume 3623 of Lecture Notes in Computer Science Volume 3623 of Theoretical Computer Science and General Issues |
| Author | Maciej Liskiewicz |
| Editors | Maciej Liskiewicz, Rüdiger Reischuk |
| Edition | illustrated |
| Publisher | Springer Science & Business Media, 2005 |
| ISBN | 3540281932, 9783540281931 |
| Length | 576 pages |
| Subjects | › › Computers / Computer Science Computers / Data Science / General Computers / Information Technology Computers / Machine Theory Computers / Programming / Algorithms Computers / Software Development & Engineering / Computer Graphics Computers / User Interfaces Mathematics / Discrete Mathematics Mathematics / Logic |
| Export Citation | BiBTeX EndNote RefMan |