Mathematical Foundations of Computer Science 2007: 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings (Lecture Notes in Computer Science, 4708)

This book constitutes the refereed proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007, held in Ceský Krumlov, Czech Republic, August 2007. The 61 revised full papers presented together with the full papers or abstracts of five invited talks address all current aspects in theoretical computer science and its mathematical foundations. Title Page Preface Organization Table of Contents How To Be Fickle Finite Model Theory on Tame Classes of Structures Introduction Tame Classes of Structures Logic and Algorithms on Tame Classes Preservation Theorems Conclusion References Minimum Cycle Bases in Graphs Algorithms and Applications References Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes Pushdown Automata and Safe Recursion Schemes Recursion Schemes and Collapsible PushdownAutomata Practical Relevance to Semantics and Verification References Evolvability Introduction Many-Argument Functions Definition of Evolvability Limits to Evolvability Some Provably Evolvable Structures Discussion References Expander Properties and the Cover Time of Random Intersection Graphs Introduction Notation, Definitions and Properties of $\Gn,m,p$ Expansion Properties of Random Intersection Graphs Bounds for the Second Eigenvalue and the Mixing Time A Useful Lemma An Upper Bound on the Cover Time Conclusions and Future Work References Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs Introduction Model and Main Result Greedy Algorithms for Independent Sets Analysis Method The Simple Case $\d = 3$ Arbitrary $d \geq 4$ References Appendix Transition Graphs of Rewriting Systems over Unranked Trees Introduction Preliminaries Partial Subtree Rewriting Systems Subtree and Flat Prefix Rewriting Systems Classification of Transition Graph Classes Reachability Via Saturation First-Order Theory Via Automatic Structures Summary and Outlook References Rewriting Conjunctive Queries Determined by Views Introduction Related Work Preliminaries Basic Definitions Determinacy Cases for Which CQ Is Complete for Rewriting Chain and Path Queries Chain Queries – Decidability Path Queries – CQ Is Almost Complete for Rewriting Determinacy and Query Equivalence Connectivity Conclusion References Approximation Algorithms for the Maximum Internal Spanning Tree Problem Introduction Notation and Basic Definitions Maximizing the Number of Internal Nodes Maximum Weighted Internal Spanning Tree General Graphs Claw-Free Graphs References New Approximability Results for 2-Dimensional Packing Problems Introduction Near-Optimum Packings with a Simple Structure Partitioning the Set of Rectangles Rounding the Lengths of the Long Rectangles Containers for Short Rectangles Rectangle Selection Selecting Long Rectangles Selecting Short-Wide and Short-Narrow Rectangles Positioning Long Rectangles and Containers Generating a Packing Packing the Long Rectangles Packing the Short-Narrow Rectangles Analysis of the Algorithm APTAS for Strip Packing Without Rotations References On Approximation of Bookmark Assignments Introduction Motivation and Formulation Previous and Our Results Related Work Organization Approximation Guarantee of a Greedy Algorithm Lower Bounds Conclusion References Height-Deterministic Pushdown Automata Introduction Preliminaries Height Determinism The General Case The Real-Time Case The Deterministic Case Other Language Classes — A Comparison Caucal’s Class Fisman and Pnueli’s Class Conclusion References Minimizing Variants of Visibly Pushdown Automata Introduction Visibly Pushdown Automata Call Driven Automata and Their Minimization Minimization of eCDA Minimization of CDA Comparison Between Different VPA Subclasses Other Results on MEVPA and SEVPA MEVPA SEVPA Block Visibly Pushdown Automata Conclusion References Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids Introduction Definitions Logic Numerical Predicates Circuits Finitely Typed Groups Results Circuits to Logic Logic to Algebra Algebra to Circuits Discussion References Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete Introduction and Previous Work Definitions and Statement of Results The Fibre Construction Notation The Fibre Gadget The Fibre Construction Remark Applications Degree Bounded CSPs Girth Restricted H-Coloring Conservative CSPs Coloring Theorems - Combinatorial Background CSP Dichotomy Classification Conjecture References NP by Means of Lifts and Shadows Introduction, Background and Previous Work Preliminaries Statement of Results NP by Means of Finitely Many Forbidden Lifts Lifts and Shadows of Dualities Proofs Applications Classes with Bounded Expansion The Classes MMSNP and FP - A Characterization On the Local Chromatic Number Summary and Future Work References The Complexity of Solitaire Introduction Preliminaries Complexity Theory Klondike Klondike Is NP-Complete Complexity of Klondike Restrictions Conclusion References Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems Introduction Simulating Parallel Algorithms in W-Stream Sorting GraphProblems Connected Components (CC) Minimum Spanning Tree (MST) Biconnected Components (BCC) Maximal Independent Set (MIS) Limits of the RPRAM Approach References Space-Conscious Compression Introduction Notation Compressing with Memory Independent of Length A Nearly Tight Upper Bound Lower Bounds Markov Sources Compressing with (Slowly) Growing Memory Window Size vs. Convergence Rate for\ LZ77 Future Work References Small Alliances in Graphs Introduction The Depth of a Graph A Probabilistic Approach References Appendix: Alliance is$\ NP$-Complete The Maximum Solution Problem on Graphs Introduction Preliminaries Methods Algebraic Framework Basic Lemmas ResultsforMAX SOL Irreflexive Graphs with $\deg(v) \leq 2$ Small Graphs ResultsforLIST MAX AW SOL Discussion and Future Work References What Are Iteration Theories Introduction Rational Theories Iteration Theories Conclusions and Future Research References Properties Complementary to Program Self-reference Introduction Notation and Preliminaries Denotational Control Structures and krt Control Structures Complementary to krt References Dobrushin Conditions for Systematic Scan with Block Dynamics Introduction Bounding the Mixing Time of Systematic Scan Application: Edge Scan on an Arbitrary Graph Application: Colouring a Tree References On the Complexity of Computing Treelength Introduction Notation, Terminology and Preliminaries Weighted $\k$ -Treelength is NP-Complete $\k$-Treelength is NP-Complete Treelength Is Hard to Approximate An Exact Algorithm the Chordal Sandwich Problem Conclusion References On Time Lookahead Algorithms for the Online Data Acknowledgement Problem Introduction Preliminaries The $f_{\rm max}$ Objective Function Algorithm Lower Bound The Sum Objective Function Algorithms Lower Bounds References Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-convex Neighborhoods Introduction Language Recognition by Cellular Automata Cellular Automata Two-Dimensional Language Recognition Iterated Neighborhoods General Form of Iterated Complete Neighborhoods MainTheorem General Behavior of $\ACA'$ Propagation of Correct Assumptions The Real Time End of the Proof Conclusion References Towards a Rice Theorem on Traces of Cellular Automata Introduction Definitions Trace The Nilpotency Problem Subtrace Problems The Full Subtrace Problem Other Problems From Subtrace to Trace Conclusion References Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority Introduction Experimental Results Analysis of Fully Asynchronous 2D Minority Energy of a Configuration Coupling with Outer-Totalistic 976 Convergence from an Arbitrary Initial Configuration Convergence from a Bounded Configuration Concluding Remarks References Public Key Identification Based on the Equivalence of Quadratic Forms Introduction The Equivalence Problem for Quadratic Forms Identification Based on the Equivalence Problem NP-Completeness Introduction and Results The Special Cohen-Lenstra Heuristics Sketch of Proofs References Proof of Proposition 44 Reachability Problems in Quaternion Matrixand Rotation Semigroups Introduction Preliminaries Word Morphisms Matrix Representations Quaternion Matrix Semigroups Computational Problems in Lipschitz Integers Geometric Interpretations References VPSPACE and a Transfer Theorem over the Complex Field Introduction Notations and Preliminaries The Blum-Shub-Smale Model Valiant’s Model The Class VPSPACE Definition An Alternative Characterization and Some Properties Testing Membership to a Union of Varieties Tests of Membership Union of Varieties Proof of the Main Theorem Satisfiable Sign Conditions Enumerating All Possibly Tested Polynomials Finding the Sign Condition of the Input A Polynomial-Time Algorithm for PAR$_{\cc}$ Problems References Efficient Provably-Secure Hierarchical Key Assignment Schemes Introduction Hierarchical Key Assignment Schemes An Encryption Based Construction Improving Key Derivation Time The Shortcutting Technique The Shortcutting and Point-Inserting Technique The Improved Shortcutting and Point-Inserting Technique A Broadcast Encryption Based Construction References Nearly Private Information Retrieval Introduction Preliminaries Our Results and Previous Work Simple Upper Bounds 1-Server Lower Bounds Perfect Privacy and Recovery Nearly Private Schemes Nearly Private Schemes with Imperfect Recovery 2-Server Lower Bounds Quantum Communication Perfect Privacy The Nearly Private Case Conclusion References Packing and Squeezing Subgraphs into Planar Graphs Introduction and Motivation Definitions Packing Trees in Planar Graphs Squeezing Planar Graphs in Planar Graphs Conclusions and Open Problems References Dynamic Matchings in Convex Bipartite Graphs Introduction Dynamic Convex Matchings The Dekel-Sahni Algorithm Overview of the Dynamic Algorithm Data Structure Supporting Status Queries The Equal Start-Points Case The Complete Data Structure PairQueries Amortized Cost of Pair Queries References Communication in Networks with RandomDependent Faults Introduction Model and Problem Definition Related Work General Networks Upper Bounds Lower Bounds Communication in the Hypercube Bounded Degree Networks Upper Bounds Lower Bounds Conclusion References Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults Introduction RelatedWorks Collision-Free Families and Fault-Tolerant Gossiping Explicit Constructions of Collision-Free Families Optimal Bounds Open Questions References A Linear Time Algorithm for the $\k$ Maximal Sums Problem Introduction Results Outline of Paper Basic Idea and Algorithm BinaryHeaps Partial Persistence and $\HU$ Construction Fredericksons Heap Selection Algorithm Combining the Ideas Extension to Higher Dimensions Space Reduction References A Lower Bound of $1+\phi$ for Truthful Scheduling Mechanisms Introduction Related Work Problem Definition A Lower Bound of $1+\phi$ for $n\rightarrow\infty$ Machines References Analysis of Maximal Repetitions in Strings Introduction Definitions The Bound Runs with Close Centers Microruns Sum of Exponents Comments FurtherResearch References Series-Parallel Languages on Scattered and Countable Posets Introduction Notation and Basic Definitions Posets Rational Languages Operations on Words Rational Languages Automata A Kleene Theorem for Scattered Posets Conclusion References Traces of Term-Automatic Graphs Introduction Notations Words, Terms and Trees Graphs Turing Machines Arborescent Tiling Systems Definitions Languages of Arborescent Tiling Systems Traces of Term-Automatic Graphs Definitions Term-Synchronous Graphs Term-Automatic Graphs Conclusion References State Complexity of Basic Operations on Suffix-Free Regular Languages Introduction Preliminaries Kleene Star and Reversal Kleene Star of Suffix-Free Regular languages Reversal of Suffix-Free Regular Languages Catenation Intersection and Union Intersection of Suffix-Free Regular Languages Union of Suffix-Free Regular Languages Conclusion References Exact Algorithms for$\ L$(2, 1)-Labeling of Graphs Introduction Exact Algorithm for Locally Injective Homomorphisms A Branching Algorithm for L(2, 1)-Labeling of Span 4 A Refined Time Analysis References On $(k,\ell)$-Leaf Powers Introduction Basic Notions and Results Some Basic Facts on $(k,\ell)$-Leaf Powers Metric Properties of $(k,\ell)$-Leaf Powers Characterisations of (4, 6)-Leaf Powers The Main Results Conclusion References An Improved Claw Finding Algorithm Using Quantum Walk Introduction Preliminaries Claw Detection Claw Finding Lower Bound References Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument Introduction Background RelatedWork Our Results Preliminaries Notations Basics of Quantum Computing Complexity Classes Locally Random Reduction Results The Case of Two Queries The Case of More Than Two Queries and Binary Answers References On the Complexity of Game Isomorphism Introduction Games, Isomorphisms, Problems, and Representations Complexity Results for Strong Isomorphism Weak and Local Isomorphism Small Case Study Comments and Open Questions References Hardness Results for Tournament Isomorphism and Automorphism Introduction Preliminaries Hardness Results for Tournament Isomorphism Hardness Results of TI for Modular Counting Classes Hardness Results of TI for NL, \sharpL, \CgleichL and PL Hardness Results of TI for DET Hardness Results for Tournament Automorphism References Relating Complete and Partial Solution for Problems Similar to Graph Automorphism Introduction Computing Graph Automorphism from Single-Vertex Solutions Other Problems Related to Graph Automorphism References Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach Introduction Preliminaries Existence of Uniform SuppNE A Graph Theoretic Approach for Constructing SuppNE SuppNE in Random Games References Selfish Load Balancing Under Partial Knowledge Introduction The Model The Structure of Nash Equilibria TheDivergenceRatio The Total Lack of Information Case, $I_i=\emptyset$ The Case of $I_i=\emptyset$ The Case of Arbitrary $I_i$ The Price of Anarchy References Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria Introduction Second Order Nash Equilibria Applications of Second Order Nash Equilibria The Prisoner’s Dilemma Braess’s Paradox Selfish Load Balancing Other Notions of Selfish Farsighted Behavior Conclusion References Congestion Games with Player-Specific Constants Introduction Framework and Preliminaries Congestion Games on Parallel Links Network Congestion Games Arbitrary Congestion Games References Finding Patterns in Given Intervals Introduction Preliminaries ProblemPMI Analysis Query Processing ProblemPMGI ProblemPMQI Conclusion References The Power of Two Prices: Beyond Cross-Monotonicity Introduction and Model Motivation The Model Related Work Contribution Two Price Cost-Sharing Forms GSP Mechanisms for Two-Price Cost-Sharing Forms $\TheFactor$-BB Two-Price Cost-Sharing Forms for Subadditive Costs Applications to Scheduling The Impact of Symmetric Costs on GSP and 1-BB Conclusion and Future Work References Semisimple Algebras of Almost Minimal Rank over the Reals Introduction A Lower Bound for $\HH\times\HH$ over $\R$ A Lower Bound for $\C^{2\times 2}$ over $\R$ Computations Not Satisfying Property (*) Computations Satisfying Property (*) Semisimple Algebras of Minimal Rank Plus One Conclusion References Structural Analysis of Gapped Motifs of a String Introduction Patterns and Motifs Equivalence of Motifs with Similar Occurrences Equivalence of Self–alignments Representation by Maximal Non–gapped Motifs References Online and Offline Access to Short Lists Introduction A New Optimal Offline Algorithm A Simple Optimal Offline Algorithmfor $\ell=3$ Randomized Lower Bounds for Small $\ell$ An Optimal Randomized Online Algorithm for $\ell$= 2 An Optimal Randomized Online Algorithm for $\ell$= 3 A Strengthened Lower Bound for General $\ell$ References Optimal Randomized Comparison Based Algorithms for Collision Introduction Related Work Preliminaries The Algorithms Deterministic or Worst-Case Time Expected Time Randomized Algorithms The Lower Bound High-Probability DAGs Easy Low-Probability Bound Expected Running Time Without Collisions Strong Low Probability Bound for Worst-Case Time Expected Time for Random Input with Collision References Randomized and Approximation Algorithms for Blue-Red Matching Introduction Problem Definition and Hardness Approximation Algorithms for Blue-Red Matching A Randomized Algorithm for Blue-Red Matching Application to Optical Networking References Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation Introduction Real Computability Subsumption of Our Results Further Related Work Overview Word-Problem for Groups The Classical Setting Presenting Real Groups Reduction$\ from$ the Real Halting Problem Basics from Group Theory and Their Presentations First Effectivity Considerations Benign Embeddings Putting It All Together References Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances Introduction Preliminaries: List Colourings and Forbidding Paths PSPACE-Completeness of \textnormal{\kcol}for $k \ge 4$ A PSPACE-Complete Problem: Sliding Tokens The Construction of Equivalent List-Colour Path Instances Tightness of the Hardness Results Graphs with Colourings at Superpolynomial Distance The Construction of the Graphs Bounds on Size and Distance References Shuffle Expressions and Words with Nested Data Introduction A Logic for Words with Nested Data Shuffle Expressions Cutting and Combining Four Kinds of Shuffle Expressions From Logic to Shuffle Expressions Ordered Shuffle Expressions Higher-Order Multicounter Automata Unordered Shuffle Expressions References Author Index Annotation This book constitutes the refereed proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007, held in Cesk?? Krumlov, Czech Republic, August 26-31, 2007. The 61 revised full papers presented together with the full papers or abstracts of 5 invited talks were carefully reviewed and selected from 167 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 Includes the refereed proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007, held in Cesky Krumlov, Czech Republic, August 2007.