Description 
1 online resource (xviii, 764 pages) : illustrations 
Series 
Lecture notes in computer science, 03029743 ; 4708 

LNCS sublibrary. SL 1, Theoretical computer science and general issues 

Lecture notes in computer science ; 4708. 03029743


LNCS sublibrary. SL 1, Theoretical computer science and general issues.

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 2Dimensional Packing Problems  On Approximation of Bookmark Assignments  Automata and Circuits  HeightDeterministic Pushdown Automata  Minimizing Variants of Visibly Pushdown Automata  Linear Circuits, TwoVariable Logic and Weakly Blocked Monoids  Complexity I  Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NPComplete  NP by Means of Lifts and Shadows  The Complexity of Solitaire  Streams and Compression  Adapting Parallel Algorithms to the WStream Model, with Applications to Graph Problems  SpaceConscious Compression  Graphs I  Small Alliances in Graphs  The Maximum Solution Problem on Graphs  Iteration and Recursion  What Are Iteration Theories?  Properties Complementary to Program Selfreference  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 Nonconvex 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 ProvablySecure 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  SeriesParallel Languages on Scattered and Countable Posets  Traces of TermAutomatic Graphs  State Complexity of Basic Operations on SuffixFree 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 PlayerSpecific Constants  Finding Patterns in Given Intervals  The Power of Two Prices: Beyond CrossMonotonicity  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 BlueRed Matching  Words and Graphs  Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation  Finding Paths Between Graph Colourings: PSPACECompleteness and Superpolynomial Distances  Shuffle Expressions and Words with Nested Data 
Summary 
Annotation 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 2631, 2007. 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, knowledgebased systems, and artificial intelligence 
Analysis 
algoritmen 

algorithms 

computeranalyse 

computer analysis 

wiskunde 

mathematics 

computerwetenschappen 

computer sciences 

computational science 

gegevensstructuren 

data structures 

Information and Communication Technology (General) 

Informatie en communicatietechnologie (algemeen) 
Bibliography 
Includes bibliographical references and index 
Notes 
English 

Print version record 
In 
Springer ebooks 
Subject 
Computer science  Mathematics  Congresses


Computer programming  Congresses


Algorithms  Congresses


Computable functions  Congresses


Machine theory  Congresses


Informatique.


Algorithms.


Computable functions.


Computer programming.


Computer science  Mathematics.


Machine theory.

Genre/Form 
Conference papers and proceedings.


Conference papers and proceedings.


Actes de congrès.

Form 
Electronic book

Author 
Kučera, Luděk.


Kučera, A. (Antonín)

ISBN 
9783540744566 

3540744568 

354074455X 

9783540744559 
