Fundamentals of Computation Theory 计算理论基础/会议录

2005-9  

北京燕山出版社  

Liskiewicz, Maciej; Reischuk, Rudiger;  

576  

This book constitutes the refereed proceedings of the 15th International Symposium Fundamentals of Computation Theory, FCT 2005, held in Lübeck, Germany in August 2005.　　The 46 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 105 submissions. The papers are organized in topical sections on circuits, automata, complexity, approximability, computational and structural complexity, graphs and complexity, computational game theory, visual cryptography and computational geometry, query complexity, distributed systems, automata and formal languages, semantics, approximation algorithms, average case complexity, algorithms, graph algorithms, and pattern matching.

Invited Talks　The Complexity of Querying External Memory and Streaming Data　The Smoothed Analysis of Algorithms Path Coupling Using Stopping TimesCircuits On the Incompressibility of Monotone DNFs Bounds on the Power of Constant-Depth Quantum CircuitsAutomata I Biautomatic Semigroups Deterministic Automata on Unranked TreesComplexity I Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals Generic Densitv and Small Span TheoremApproximability Logspace Optimization Problems and Their Approximability Properties A Faster and Simpler 2-Approximation Algorithm for Block SortingComputational and Structural Complexity On the Power of Unambiguity in Alternating Machines Translational Lemmas for Alternating TMs and PRAMs Collapsing Recursive Oracles for Relativized Polynomial HierarchiesGraphs and Complexity Exact Algorithms for Graph Homomorphisms Improved Algorithms and Complexity Results for Power Domination in Graphs Clique-Width for Four-Vertex Forbidden SubgraphsComputational Game Theory On the Complexity of Uniformly Mixed Nash Equilibria and RelatedRegular Subgraph Problems Simple Stochastic Games and P-Matrix Generalized Linear Complementarity ProblemsVisual Cryptography and Computational Geometry Perfect Reconstruction of Black Pixels Revisited Adaptive Zooming in Point Set LabelingQuery ComplexityGraph AlgorithmsApproximation AlgorithmsAverage-Case Compexity AlgorithmsComplexityⅡGraph AlgorithmsAutomataⅡPattern Matching Author Index

Fundamentals of Computation Theory 计算理论基础/会议录 PDF格式下载