Vašek Chvátal (auth.), Luděk Kučera, Antonín Kučera (eds.)354074455X, 9783540744559
The 61 revised full papers presented together with the full papers or abstracts of 5 invited talks were carefully reviewed and selected from 167 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, ranging from algorithms and data structures, to complexity, automata, semantics, logic, formal specifications, models of computation, concurrency theory, computational geometry, parallel and distributed computing, networks, bioinformatics, quantum computing, cryptography, knowledge-based systems, and artificial intelligence.
Table of contents :
Front Matter….Pages –
How To Be Fickle….Pages 1-1
Finite Model Theory on Tame Classes of Structures….Pages 2-12
Minimum Cycle Bases in Graphs Algorithms and Applications….Pages 13-14
Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes….Pages 15-21
Evolvability….Pages 22-43
Expander Properties and the Cover Time of Random Intersection Graphs….Pages 44-55
Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs….Pages 56-66
Transition Graphs of Rewriting Systems over Unranked Trees….Pages 67-77
Rewriting Conjunctive Queries Determined by Views….Pages 78-89
Approximation Algorithms for the Maximum Internal Spanning Tree Problem….Pages 90-102
New Approximability Results for 2-Dimensional Packing Problems….Pages 103-114
On Approximation of Bookmark Assignments….Pages 115-124
Height-Deterministic Pushdown Automata….Pages 125-134
Minimizing Variants of Visibly Pushdown Automata….Pages 135-146
Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids….Pages 147-158
Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete….Pages 159-170
NP by Means of Lifts and Shadows….Pages 171-181
The Complexity of Solitaire….Pages 182-193
Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems….Pages 194-205
Space-Conscious Compression….Pages 206-217
Small Alliances in Graphs….Pages 218-227
The Maximum Solution Problem on Graphs….Pages 228-239
What Are Iteration Theories?….Pages 240-252
Properties Complementary to Program Self-reference….Pages 253-263
Dobrushin Conditions for Systematic Scan with Block Dynamics….Pages 264-275
On the Complexity of Computing Treelength….Pages 276-287
On Time Lookahead Algorithms for the Online Data Acknowledgement Problem….Pages 288-297
Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-convex Neighborhoods….Pages 298-309
Towards a Rice Theorem on Traces of Cellular Automata….Pages 310-319
Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority….Pages 320-332
Public Key Identification Based on the Equivalence of Quadratic Forms….Pages 333-345
Reachability Problems in Quaternion Matrix and Rotation Semigroups….Pages 346-358
VPSPACE and a Transfer Theorem over the Complex Field….Pages 359-370
Efficient Provably-Secure Hierarchical Key Assignment Schemes….Pages 371-382
Nearly Private Information Retrieval….Pages 383-393
Packing and Squeezing Subgraphs into Planar Graphs….Pages 394-405
Dynamic Matchings in Convex Bipartite Graphs….Pages 406-417
Communication in Networks with Random Dependent Faults….Pages 418-429
Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults….Pages 430-441
A Linear Time Algorithm for the k Maximal Sums Problem….Pages 442-453
A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms….Pages 454-464
Analysis of Maximal Repetitions in Strings….Pages 465-476
Series-Parallel Languages on Scattered and Countable Posets….Pages 477-488
Traces of Term-Automatic Graphs….Pages 489-500
State Complexity of Basic Operations on Suffix-Free Regular Languages….Pages 501-512
Exact Algorithms for L (2,1)-Labeling of Graphs….Pages 513-524
On ( k ,ℓ)-Leaf Powers….Pages 525-535
An Improved Claw Finding Algorithm Using Quantum Walk….Pages 536-547
Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument….Pages 548-558
On the Complexity of Game Isomorphism….Pages 559-571
Hardness Results for Tournament Isomorphism and Automorphism….Pages 572-583
Relating Complete and Partial Solution for Problems Similar to Graph Automorphism….Pages 584-595
Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach….Pages 596-608
Selfish Load Balancing Under Partial Knowledge….Pages 609-620
Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria….Pages 621-632
Congestion Games with Player-Specific Constants….Pages 633-644
Finding Patterns in Given Intervals….Pages 645-656
The Power of Two Prices: Beyond Cross-Monotonicity….Pages 657-668
Semisimple Algebras of Almost Minimal Rank over the Reals….Pages 669-680
Structural Analysis of Gapped Motifs of a String….Pages 681-690
Online and Offline Access to Short Lists….Pages 691-702
Optimal Randomized Comparison Based Algorithms for Collision….Pages 703-714
Randomized and Approximation Algorithms for Blue-Red Matching….Pages 715-725
Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation….Pages 726-737
Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances….Pages 738-749
Shuffle Expressions and Words with Nested Data….Pages 750-761
Back Matter….Pages –
Reviews
There are no reviews yet.