Mathematical Foundations of Computer Science 2001 计算机科学的数学基础2001

The LNCS series reports state-of-the-art results in computer science research, development, and education, at a high level and in both printed and electronic form. Enjoying tight cooperation with the R&D community, with numerous individuals, as well as with prestigious organizations and Societies, LNCS has grown into the most comprehensive computer science research forum available.
The scope of LNCS, including its sub series LNAI, spans the whole range of computer science and information technology including interdisciplinary topics in a variety of application fields. The type of material published traditionally includes
　　- Proceedings (published in time for the respective conference)
　 - Post-proceedings (consisting of thoroughly revised final full papers)
　 -research monographs (which may be based on outstanding PhD work, research projects, technical reports, etc.)

在线阅读本书

This book constitutes the refereed proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, MFCS 2001, held in Marianske Lazne, Czech Republic in August 2001. The 51 revised full papers presented together with 10 invited contributions were carefully reviewed and selected from a total of 118 submissions. All current aspects of theoretical computer science are addressed ranging from mathematical logic and programming theory to algorithms, discrete mathematics, and complexity theory. Besides classical issues, modern topics like quantum computing are discussed as well.

Invited Talks
　A New Category for Semantics
　On Implications between P-NP-Hypotheses:Decision versus Computation in Algebraic Complexity
　Playing Games with Algorithms:Algorithmic Combinatorial Game Theory
　Some Recent Results on Data Mining and Search
　Hyper tree Decompositions: A Survey
　The Strength of Non-size-increasing Computation(Introduction and Summary)
　Introduction to Recent Quantum Algorithms
　Decomposition Methods and Sampling Circuits in the Cartesian Lattice
　New Algorithms for k-SAT Based on the Local Search Principle
　Linear Temporal Logic and Finite Semi groups
Contributed Talks
　Refined Search Tree Technique for DOMINATING SET on Planar Graphs
　The Computational Power of a Family of Decision Forests
　Exact Results for Accepting Probabilities of Quantum Axiomatic
　Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms
　Analysis Problems for Sequential Dynamical Systems and Communicating State Machines
　The Complexity of Tensor Circuit Evaluation (Extended Abstract)
　Computing Reciprocals of Bivariate Power Series
　Automatic Verification of Recursive Procedures with One Integer Parameter
　Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds Computable Versions of Baire's Category Theorem
　Automata on Linear Orderings
　Algorithmic Information Theory and Cellular Automata Dynamics
　The k-Median Problem for Directed Trees (Extended Abstract)
　On Pseudorandom Generators in NC0
　There Are No Sparse NPw-Hard Sets
　Sharing One Secret vs. Sharing Many Secrets: Tight Bounds for the Max Improvement Ratio
　(H, C, K)-Coloring: Fast, Easy, and Hard Cases
　Randomness and Reducibility
　On the Computational Complexity of Infinite Words
　Lower Bounds for On-Line Single-Machine Scheduling
……