## Mathematical Foundations of Computer Science 2007: 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007, ProceedingsThis 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

How To Be Fickle | 1 |

Finite Model Theory on Tame Classes of Structures | 2 |

Minimum Cycle Bases in Graphs Algorithms and Applications | 13 |

Hierarchies of Inﬁnite Structures Generated by Pushdown Automata and Recursion Schemes | 15 |

Evolvability | 22 |

Expander Properties and the Cover Time of Random Intersection Graphs | 44 |

Independent Sets in Random Regular Graphs | 56 |

Transition Graphs of Rewriting Systems over Unranked Trees | 67 |

Nearly Private Information Retrieval | 383 |

Packing and Squeezing Subgraphs into Planar Graphs | 394 |

Dynamic Matchings in Convex Bipartite Graphs | 406 |

Communication in Networks with Random Dependent Faults | 418 |

Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults Extended Abstract | 430 |

A Linear Time Algorithm for the k Maximal Sums Problem | 442 |

A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms | 454 |

Analysis of Maximal Repetitions in Strings | 465 |

Rewriting Conjunctive Queries Determined by Views | 78 |

Approximation Algorithms for the Maximum Internal Spanning Tree Problem | 90 |

New Approximability Results for 2Dimensional Packing Problems | 103 |

On Approximation of Bookmark Assignments | 115 |

HeightDeterministic Pushdown Automata | 125 |

Minimizing Variants of Visibly Pushdown Automata | 135 |

Linear Circuits TwoVariable Logic and Weakly Blocked Monoids | 147 |

Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NPComplete | 159 |

NP by Means of Lifts and Shadows | 171 |

The Complexity of Solitaire | 182 |

Adapting Parallel Algorithms to the WStream Model with Applications to Graph Problems | 194 |

SpaceConscious Compression | 206 |

Small Alliances in Graphs | 218 |

The Maximum Solution Problem on Graphs | 228 |

What Are Iteration Theories? | 240 |

Properties Complementary to Program Selfreference | 253 |

Dobrushin Conditions for Systematic Scan with Block Dynamics | 264 |

On the Complexity of Computing Treelength | 276 |

On Time Lookahead Algorithms for the Online Data Acknowledgement Problem | 288 |

Dealing with Nonconvex Neighborhoods | 298 |

Towards a Rice Theorem on Traces of Cellular Automata | 310 |

A Study of Asynchronous 2D Minority | 320 |

Public Key Identiﬁcation Based on the Equivalence of Quadratic Forms | 333 |

Reachability Problems in Quaternion Matrix and Rotation Semigroups | 346 |

VPSPACE and a Transfer Theorem over the Complex Field | 359 |

Efficient ProvablySecure Hierarchical Key Assignment Schemes | 371 |

SeriesParallel Languages on Scattered and Countable Posets | 477 |

Traces of TermAutomatic Graphs | 489 |

State Complexity of Basic Operations on SuffixFree Regular Languages | 501 |

Exact Algorithms for L2 1Labeling of Graphs | 513 |

On klLeaf Powers | 525 |

An Improved Claw Finding Algorithm Using Quantum Walk | 536 |

Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument | 548 |

On the Complexity of Game Isomorphism Extended Abstract | 559 |

Hardness Results for Tournament Isomorphism and Automorphism | 572 |

Relating Complete and Partial Solution for Problems Similar to Graph Automorphism | 584 |

A Graph Theoretic Approach | 596 |

Selﬁsh Load Balancing Under Partial Knowledge | 609 |

Second Order Nash Equilibria | 621 |

Congestion Games with PlayerSpeciﬁc Constants | 633 |

Finding Patterns in Given Intervals | 645 |

Beyond CrossMonotonicity | 657 |

Semisimple Algebras of Almost Minimal Rank over the Reals | 669 |

Structural Analysis of Gapped Motifs of a String | 681 |

Online and Offline Access to Short Lists | 691 |

Optimal Randomized Comparison Based Algorithms for Collision | 703 |

Randomized and Approximation Algorithms for BlueRed Matching | 715 |

The Word Problem for a Class of Groups with Inﬁnite Presentation Extended Abstract | 726 |

PSPACECompleteness and Superpolynomial Distances | 738 |

Shuffle Expressions and Words with Nested Data | 750 |

762 | |

### Other editions - View all

### Common terms and phrases

algebra algorithm alphabet approximation approximation algorithm automata automaton automorphism Berlin Heidelberg 2007 cell cellular automata chordal chordal graphs color complexity Computer Science conﬁguration congestion games consider constant construction cost define deﬁned Deﬁnition denote diﬀerent edges elements equilibria equivalent exists ﬁnite ﬁrst ﬁxed forall forany function given graph G Heidelberg homomorphism IEEE inﬁnite input integer intersection graphs isan isomorphism Kuˇcera Eds labeled languages Lemma length Let G linear LNCS lower bound matching matrix MFCS minimal morphism Nash equilibrium node non-trivial automorphism NP-complete NP-hard obtain ofall optimal output path planar graph players polynomial posets probability problem Proof properties Proposition pushdown pushdown automata quantum quaternion queries random rectangles recursion regular languages rewriting Springer structure subgraphs subset supernodes Theorem theory trees update upper bound variables vector vertex vertices W-Stream wecan weshow