Mathematical foundations of computer science 2002(计算机科学的数学基础2002)

This book constitutes the refereed proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002, held in Warsaw, Poland in August 2002.The 48 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 108 submissions. All relevant aspects of theoretical computer science are addressed, ranging from discrete mathematics, combinatorial optimization, graph theory, algorithms, and complexity to programming theory, formal methods, and mathematical logic.

在线阅读本书

This book constitutes the refereed proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002, held in Warsaw, Poland in August 2002.The 48 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 108 submissions. All relevant aspects of theoretical computer science are addressed, ranging from discrete mathematics, combinatorial optimization, graph theory, algorithms, and complexity to programming theory, formal methods, and mathematical logic.

Invited Talks
　Global Development via Local Observational Construction Steps
　Edge-Colouring Pairs of Binary Trees　Towards a Concise Proof of the Four-Colour Theorem of Planar Maps
　Applications of Finite Automata　Approximability of the Minimum Bisection Problem
An Algorithmic Challenge
　Low Stretch Spanning Trees
Contributed Talks
　On Radiocoloring Hierarchically Specified Planar Graphs　PSP ACB-Completeness and Approximations
　Finite Domain Constraint Satisfaction Using Quantum Computation
　Fast Algorithms with Algebraic Monge Properties
　Packing Edges in Random Regular Graphs
　A Lower Bound Technique for Nondeterministic Graph-Driven　Read-Once-Branching Programs and Its Applications
　Matroid Intersections, Polymatroid Inequalities, and Related Problems
　Accessibility in Automata on Scattered Linear Orderings
　On Infinite Terms Having a Decidable Monadic Theory
　A Chomsky-Like Hierarchy of Infinite Graphs
　Competitive Analysis of On-line Stream Merging Algorithms
　Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time　via Semidefinite Programming
　On word Equauons in une variable
　Autoreducibility of Random Sets:　A Sharp Bound on the Density of Guessed Bits
　Two-Way Finite State Transducers with Nested Pebbles
　Optimal Non-preemptive Semi-online Scheduling　on Two Related Machines
　More on Weighted Servers or FIFO is Better than LRU
　On Maximizing the Throughput of Multiprocessor Tasks
　Some Results on Random Unsatisfiable k-Sat Instances 　and Approximation Algorithms Applied to Random Structures
　Evolutive Tandem Repeats Using Hamming Distance
　Subgraph Isomorphism, log-Bounded Fragmentation　and Graphs of (Locally) Bounded Treewidth
　Computing Partial Information out of Intractable One 　The First Digit of 2n at Base 3 as an Example
　Algorithms for Computing Small NFAs
……
Author Index