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