Mathematical Foundations of Computer Science 2007 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings /
| Corporate Author: | |
|---|---|
| Other Authors: | , |
| Language: | English |
| Published: |
Berlin, Heidelberg :
Springer Berlin Heidelberg : Imprint: Springer,
2007.
|
| Edition: | 1st ed. 2007. |
| Series: | Theoretical Computer Science and General Issues ;
4708 |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/978-3-540-74456-6 |
Table of Contents:
- 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.