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

出版社：湖北辞书出版社  作者：Kralovic, Rastislav; Urzyczyn, Pawel;  页数：814  

内容概要

This book constitutes the refereed proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, MFCS 2006, held in Stará Lesná, Slovakia in August/September 2006.    The 62 revised full papers presented together with the full papers or abstracts of 7 invited talks were carefully reviewed and selected from 174 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, ranging from algorithms and data structures, to complexity, automata, semantics, logic, formal specifications, models of computation, concurrency theory, computational geometry, parallel and distributed computing, networks, bioinformatics, quantum computing, cryptography, knowledge-based systems, and artificial intelligence.

书籍目录

Invited Talks  A Core Calculus for Scala Type Checking  Tree Exploration with an Oracle  Distributed Data Structures: A Survey on Informative Labeling Schemes  From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of   Deductions  The Structure of Tractable Constraint Satisfaction Problems  On the Representation of Kleene Algebras with Tests  From Three Ideas in TCS to Three Applications in BioinformaticsContributed Papers  Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles  Approximate Shortest Path Queries on Weighted Polyhedral Surfaces  A Unified Construction of the Glushkov, Follow, and Antimirov Automata  Algebraic Characterizations of Unitary Linear Quantum Cellular Automata   A Polynomial Time Nilpotence Test for Galois Groups and Related Results  The Multiparty Communication Bounds and New Problems  Crochemore Factorization of Sturmian and Other Infinite Words  Equations on Partial Words  Concrete Multiplicative Complexity of Symmetric Functions  On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures  Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities  The Kleene Equality for Graphs  On the Repetition Threshold for Large Alphabets  hnproved Parameterized Upper Bounds for Vertex Cover  On Comparing Sums of Square Roots of Small Integers  A Combinatorial Approach to Collapsing Words  Optimal Linear Arrangement of Interval Graphs  The Lempel-Ziv Complexity of Fixed Points of Morphisms  Partially Commutative Inverse Monoids  Learning Bayesian Networks Does Not Have to Be NP-Hard……Author Index