Mathematical Foundations of Computer Science 2007 [electronic resource] : 32nd International Symposium, MFCS 2007 Český Krumlov, Czech Republic, August 26-31, 2007 Proceedings / edited by Luděk Kučera, Antonín Kučera.

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 -- Congestion Games 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.