Mathematical Foundations of Computer Science 2006: 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006. Proceedings

Front Matter....Pages -
A Core Calculus for Scala Type Checking....Pages 1-23
Tree Exploration with an Oracle....Pages 24-37
Distributed Data Structures: A Survey on Informative Labeling Schemes....Pages 38-38
From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of Deductions....Pages 39-57
The Structure of Tractable Constraint Satisfaction Problems....Pages 58-72
On the Representation of Kleene Algebras with Tests....Pages 73-83
From Three Ideas in TCS to Three Applications in Bioinformatics....Pages 84-85
Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles....Pages 86-97
Approximate Shortest Path Queries on Weighted Polyhedral Surfaces....Pages 98-109
A Unified Construction of the Glushkov, Follow, and Antimirov Automata....Pages 110-121
Algebraic Characterizations of Unitary Linear Quantum Cellular Automata....Pages 122-133
A Polynomial Time Nilpotence Test for Galois Groups and Related Results....Pages 134-145
The Multiparty Communication Complexity of Exact- T : Improved Bounds and New Problems....Pages 146-156
Crochemore Factorization of Sturmian and Other Infinite Words....Pages 157-166
Equations on Partial Words....Pages 167-178
Concrete Multiplicative Complexity of Symmetric Functions....Pages 179-189
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures....Pages 190-201
Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities....Pages 202-213
The Kleene Equality for Graphs....Pages 214-225
On the Repetition Threshold for Large Alphabets....Pages 226-237
Improved Parameterized Upper Bounds for Vertex Cover....Pages 238-249
On Comparing Sums of Square Roots of Small Integers....Pages 250-255
A Combinatorial Approach to Collapsing Words....Pages 256-266
Optimal Linear Arrangement of Interval Graphs....Pages 267-279
The Lempel-Ziv Complexity of Fixed Points of Morphisms....Pages 280-291
Partially Commutative Inverse Monoids....Pages 292-304
Learning Bayesian Networks Does Not Have to Be NP-Hard....Pages 305-314
Lower Bounds for the Transition Complexity of NFAs....Pages 315-326
Smart Robot Teams Exploring Sparse Trees....Pages 327-338
 k -Sets of Convex Inclusion Chains of Planar Point Sets....Pages 339-350
Toward the Eigenvalue Power Law....Pages 351-362
Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves....Pages 363-374
Very Sparse Leaf Languages....Pages 375-386
On the Correlation Between Parity and Modular Polynomials....Pages 387-398
Optimally Fast Data Gathering in Sensor Networks....Pages 399-411
Magic Numbers in the State Hierarchy of Finite Automata....Pages 412-423
Online Single Machine Batch Scheduling....Pages 424-435
Machines that Can Output Empty Words....Pages 436-446
Completeness of Global Evaluation Logic....Pages 447-458
NOF-Multiparty Information Complexity Bounds for Pointer Jumping....Pages 459-470
Dimension Characterizations of Complexity Classes....Pages 471-479
Approximation Algorithms and Hardness Results for Labeled Connectivity Problems....Pages 480-491
An Expressive Temporal Logic for Real Time....Pages 492-504
On Matroid Representability and Minor Problems....Pages 505-516
Non-cooperative Tree Creation....Pages 517-527
Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners....Pages 528-539
Reductions for Monotone Boolean Circuits....Pages 540-548
Generalised Integer Programming Based on Logically Defined Relations....Pages 549-560
Probabilistic Length-Reducing Automata....Pages 561-572
Sorting Long Sequences in a Single Hop Radio Network....Pages 573-583
Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture....Pages 584-595
Valiant’s Model: From Exponential Sums to Exponential Products....Pages 596-607
A Reachability Algorithm for General Petri Nets Based on Transition Invariants....Pages 608-621
Approximability of Bounded Occurrence Max Ones....Pages 622-633
Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability....Pages 634-645
Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes....Pages 646-657
Quantum Weakly Nondeterministic Communication Complexity....Pages 658-669
Minimal Chordal Sense of Direction and Circulant Graphs....Pages 670-680
Querying and Embedding Compressed Texts....Pages 681-692
Lempel-Ziv Dimension for Lempel-Ziv Compression....Pages 693-703
Characterizing Valiant’s Algebraic Complexity Classes....Pages 704-716
The Price of Defense....Pages 717-728
The Data Complexity of MDatalog in Basic Modal Logics....Pages 729-740
The Complexity of Counting Functions with Easy Decision Version....Pages 741-752
On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model....Pages 753-764
Constrained Minimum Enclosing Circle with Center on a Query Line Segment....Pages 765-776
Hierarchical Unambiguity....Pages 777-788
An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture....Pages 789-800
On Genome Evolution with Innovation....Pages 801-811
Back Matter....Pages -