Physical description 
1 online resource (xiv, 626 pages) : illustrations. 
Series 
Lecture notes in computer science, 03029743 ; 5162


Lecture notes in computer science ; 5162. 03029743


Springer Lecture Notes in Computer Science

Bibliography 
Includes bibliographical references and author index. 
Contents 
Invited Papers  One Useful Logic That Defines Its Own Truth  On Synchronous and Asynchronous Interaction in Distributed Systems  A Robust Class of Regular Languages  Deterministic Models of Communication Faults  Algebraic Graph Algorithms  Contributed Papers  Question/Answer Games on Towers and Pyramids  The Maximum Independent Set Problem in Planar Graphs  When Ignorance Helps: Graphical Multicast Cost Sharing Games  Shortest Synchronizing Strings for Huffman Codes  Optimizing Conjunctive Queries over Trees Using Schema Information  Clustering with Partial Information  Reoptimization of the Metric Deadline TSP  On the Shortest Linear StraightLine Program for Computing Linear Forms  Flip Algorithm for Segment Triangulations  Computing Sharp 2Factors in ClawFree Graphs  A 6/5Approximation Algorithm for the Maximum 3Cover Problem  Positional Strategies for HigherOrder Pushdown Parity Games  Arthur and Merlin as Oracles  A Decision Problem for Ultimately Periodic Sets in Nonstandard Numeration Systems  Regional Languages and Tiling: A Unifying Approach to Picture Grammars  On a Special Class of Primitive Words  Complexity of Data Tree Patterns over XML Documents  A PTAS for the Sparsest Spanners Problem on ApexMinorFree Graphs  Computational Complexity of PerfectPhylogenyRelated Haplotyping Problems  SincereStrategy PreferenceBased Approval Voting Broadly Resists Control  ReversalBounded Counter Machines Revisited  Iterative Compression and Exact Algorithms  Complexity and Limiting Ratio of Boolean Functions over Implication  Succinctness of Regular Expressions with Interleaving, Intersection and Counting  Nilpotency and Limit Sets of Cellular Automata  A Note on kColorability of P 5Free Graphs  Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations  Lower Bounds for Syntactically Multilinear Algebraic Branching Programs  Periodicity and Immortality in Reversible Computing  StepOut Ring Signatures  The Height of Factorization Forests  Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae  Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise  From?Calculus to Universal Algebra and Back  A Complete Axiomatic System for a ProcessBased Spatial Logic  Voronoi Games on Cycle Graphs  Colouring Random Empire Trees  A Random Oracle Does Not Help Extract the Mutual Information  Approximating Independent Set and Coloring in Random Uniform Hypergraphs  A New Upper Bound for Max2SAT: A GraphTheoretic Approach  Directed Percolation Arising in Stochastic Cellular Automata Analysis  Resolution Width and Cutting Plane Rank Are Incomparable  On the Decidability of Bounded Valuedness for Transducers  Monadic Second Order Logic on Graphs with Local Cardinality Constraints  Short Proofs of Strong Normalization. 
Summary 
Annotation This book constitutes the refereed proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008, held in Torun, Poland, in August 2008. The 45 revised full papers presented together with 5 invited lectures were carefully reviewed and selected from 119 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, ranging from algorithmic game theory, algorithms and data structures, artificial intelligence, automata and formal languages, bioinformatics, complexity, concurrency and petrinets, cryptography and security, logic and formal specifications, models of computations, parallel and distributed computing, semantics and verification. 
Other author 
Ochmanski, Edward.


Tyszkiewicz, Jerzy.


SpringerLink issuing body.

Subject 
Computer science  Mathematics  Congresses.


Computer programming  Congresses.


Algorithms  Congresses.


Machine theory  Congresses.


Electronic books. 

Conference papers and proceedings. 
Variant Title 
MFCS 2008 
ISBN 
9783540852384 

3540852387 

9783540852377 

3540852379 
Standard Number 
10.1007/9783540852384 
