Fundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005. Proceedings /
| Συγγραφή απο Οργανισμό/Αρχή: | |
|---|---|
| Άλλοι συγγραφείς: | , |
| Μορφή: | Ηλεκτρονική πηγή Ηλ. βιβλίο |
| Γλώσσα: | English |
| Έκδοση: |
Berlin, Heidelberg :
Springer Berlin Heidelberg,
2005.
|
| Σειρά: | Lecture Notes in Computer Science,
3623 |
| Θέματα: | |
| Διαθέσιμο Online: | Full Text via HEAL-Link |
Πίνακας περιεχομένων:
- Invited Talks
- The Complexity of Querying External Memory and Streaming Data
- The Smoothed Analysis of Algorithms
- Path Coupling Using Stopping Times
- Circuits
- On the Incompressibility of Monotone DNFs
- Bounds on the Power of Constant-Depth Quantum Circuits
- Automata I
- Biautomatic Semigroups
- Deterministic Automata on Unranked Trees
- Complexity I
- Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals
- Generic Density and Small Span Theorem
- Approximability
- Logspace Optimization Problems and Their Approximability Properties
- A Faster and Simpler 2-Approximation Algorithm for Block Sorting
- Computational and Structural Complexity
- On the Power of Unambiguity in Alternating Machines
- Translational Lemmas for Alternating TMs and PRAMs
- Collapsing Recursive Oracles for Relativized Polynomial Hierarchies
- Graphs and Complexity
- Exact Algorithms for Graph Homomorphisms
- Improved Algorithms and Complexity Results for Power Domination in Graphs
- Clique-Width for Four-Vertex Forbidden Subgraphs
- Computational Game Theory
- On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems
- Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems
- Visual Cryptography and Computational Geometry
- Perfect Reconstruction of Black Pixels Revisited
- Adaptive Zooming in Point Set Labeling
- Query Complexity
- On the Black-Box Complexity of Sperner’s Lemma
- Property Testing and the Branching Program Size of Boolean Functions
- Distributed Systems
- Almost Optimal Explicit Selectors
- The Delayed k-Server Problem
- Automata and Formal Languages
- Leftist Grammars and the Chomsky Hierarchy
- Shrinking Multi-pushdown Automata
- Graph Algorithms
- A Simple and Fast Min-cut Algorithm
- (Non)-Approximability for the Multi-criteria TSP(1,2)
- Semantics
- Completeness and Compactness of Quantitative Domains
- A Self-dependency Constraint in the Simply Typed Lambda Calculus
- A Type System for Computationally Secure Information Flow
- Approximation Algorithms
- Algorithms for Graphs Embeddable with Few Crossings Per Edge
- Approximation Results for the Weighted P 4 Partition Problems
- The Maximum Resource Bin Packing Problem
- Average-Case Complexity
- Average-Case Non-approximability of Optimisation Problems
- Relations Between Average-Case and Worst-Case Complexity
- Algorithms
- Reconstructing Many Partitions Using Spectral Techniques
- Constant Time Generation of Linear Extensions
- Complexity II
- On Approximating Real-World Halting Problems
- An Explicit Solution to Post’s Problem over the Reals
- The Complexity of Semilinear Problems in Succinct Representation
- Graph Algorithms
- On Finding Acyclic Subhypergraphs
- An Improved Approximation Algorithm for TSP with Distances One and Two
- New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem
- Automata II
- On the Expressiveness of Asynchronous Cellular Automata
- Tree Automata and Discrete Distributed Games
- Pattern Matching
- A New Linearizing Restriction in the Pattern Matching Problem
- Fully Incremental LCS Computation.
