Mathematical Foundations of Computer Science 2007

Invited Papers.- How To Be Fickle.- Finite Model Theory on Tame Classes of Structures.- Minimum Cycle Bases in Graphs Algorithms and Applications.- Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes.- Evolvability.- Random Graphs.- Expander Properties and the Cover Time of Random Intersection Graphs.- Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs.- Rewriting.- Transition Graphs of Rewriting Systems over Unranked Trees.- Rewriting Conjunctive Queries Determined by Views.- Approximation Algorithms.- Approximation Algorithms for the Maximum Internal Spanning Tree Problem.- New Approximability Results for 2-Dimensional Packing Problems.- On Approximation of Bookmark Assignments.- Automata and Circuits.- Height-Deterministic Pushdown Automata.- Minimizing Variants of Visibly Pushdown Automata.- Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids.- Complexity I.- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete.- NP by Means of Lifts and Shadows.- The Complexity of Solitaire.- Streams and Compression.- Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems.- Space-Conscious Compression.- Graphs I.- Small Alliances in Graphs.- The Maximum Solution Problem on Graphs.- Iteration and Recursion.- What Are Iteration Theories?.- Properties Complementary to Program Self-reference.- Algorithms I.- Dobrushin Conditions for Systematic Scan with Block Dynamics.- On the Complexity of Computing Treelength.- On Time Lookahead Algorithms for the Online Data Acknowledgement Problem.- Automata.- Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-convex Neighborhoods.- Towards a Rice Theorem on Traces of Cellular Automata.- Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority.- Complexity II.- Public Key Identification Based on the Equivalence of Quadratic Forms.- Reachability Problems in Quaternion Matrix and Rotation Semigroups.- VPSPACE and a Transfer Theorem over the Complex Field.- Protocols.- Efficient Provably-Secure Hierarchical Key Assignment Schemes.- Nearly Private Information Retrieval.- Graphs II.- Packing and Squeezing Subgraphs into Planar Graphs.- Dynamic Matchings in Convex Bipartite Graphs.- Networks.- Communication in Networks with Random Dependent Faults.- Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults.- Algorithms II.- A Linear Time Algorithm for the k Maximal Sums Problem.- A Lower Bound of 1?+?? for Truthful Scheduling Mechanisms.- Analysis of Maximal Repetitions in Strings.- Languages.- Series-Parallel Languages on Scattered and Countable Posets.- Traces of Term-Automatic Graphs.- State Complexity of Basic Operations on Suffix-Free Regular Languages.- Graphs III.- Exact Algorithms for L(2,1)-Labeling of Graphs.- On (k,?)-Leaf Powers.- Quantum Computing.- An Improved Claw Finding Algorithm Using Quantum Walk.- Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument.- Isomorphism.- On the Complexity of Game Isomorphism.- Hardness Results for Tournament Isomorphism and Automorphism.- Relating Complete and Partial Solution for Problems Similar to Graph Automorphism.- Equilibria.- Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach.- Selfish Load Balancing Under Partial Knowledge.- Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria.- Games.- CongestionGames with Player-Specific Constants.- Finding Patterns in Given Intervals.- The Power of Two Prices: Beyond Cross-Monotonicity.- Algebra and Strings.- Semisimple Algebras of Almost Minimal Rank over the Reals.- Structural Analysis of Gapped Motifs of a String.- Algorithms III.- Online and Offline Access to Short Lists.- Optimal Randomized Comparison Based Algorithms for Collision.- Randomized and Approximation Algorithms for Blue-Red Matching.- Words and Graphs.- Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation.- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances.- Shuffle Expressions and Words with Nested Data.