Fundamentals of Computation Theory: 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings

Front Cover
Springer Science & Business Media, Aug 4, 2005 - Computers - 576 pages
This 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
Author Index
575
Copyright

Other editions - View all

Common terms and phrases