Mathematical Foundations of Computer Science 2007: 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings

Front Cover
Springer Science & Business Media, Aug 15, 2007 - Computers - 764 pages

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.

 

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 Infinite 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 Identification 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
Selfish Load Balancing Under Partial Knowledge
609
Second Order Nash Equilibria
621
Congestion Games with PlayerSpecific 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 Infinite Presentation Extended Abstract
726
PSPACECompleteness and Superpolynomial Distances
738
Shuffle Expressions and Words with Nested Data
750
Author Index
762
Copyright

Other editions - View all

Common terms and phrases