Mathematical Foundations of Computer Science 2006

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 Bioinformatics.- Contributed 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 Complexity of Exact-T: Improved 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.- Improved 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.- Lower Bounds for the Transition Complexity of NFAs.- Smart Robot Teams Exploring Sparse Trees.- k-Sets of Convex Inclusion Chains of Planar Point Sets.- Toward the Eigenvalue Power Law.- Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves.- Very Sparse Leaf Languages.- On the Correlation Between Parity and Modular Polynomials.- Optimally Fast Data Gathering in Sensor Networks.- Magic Numbers in the State Hierarchy of Finite Automata.- Online Single Machine Batch Scheduling.- Machines that Can Output Empty Words.- Completeness of Global Evaluation Logic.- NOF-Multiparty Information Complexity Bounds for Pointer Jumping.- Dimension Characterizations of Complexity Classes.- Approximation Algorithms and Hardness Results for Labeled Connectivity Problems.- An Expressive Temporal Logic for Real Time.- On Matroid Representability and Minor Problems.- Non-cooperative Tree Creation.- Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners.- Reductions for Monotone Boolean Circuits.- Generalised Integer Programming Based on Logically Defined Relations.- Probabilistic Length-Reducing Automata.- Sorting Long Sequences in a Single Hop Radio Network.- Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture.- Valiant’s Model: From Exponential Sums to Exponential Products.- A Reachability Algorithm for General Petri Nets Based on Transition Invariants.- Approximability of Bounded Occurrence Max Ones.- Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability.- Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes.- Quantum Weakly Nondeterministic Communication Complexity.- Minimal Chordal Sense of Direction and Circulant Graphs.- Querying and Embedding Compressed Texts.- Lempel-Ziv Dimension for Lempel-Ziv Compression.- Characterizing Valiant’s Algebraic Complexity Classes.- The Price of Defense.- The Data Complexity of MDatalog in Basic Modal Logics.- The Complexity of Counting Functions with Easy Decision Version.- On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model.- Constrained Minimum Enclosing Circle with Center on a Query Line Segment.- Hierarchical Unambiguity.- An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the ?erny Conjecture.- On Genome Evolution with Innovation.