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

Lecture notes in computer science ; 5162. 03029743

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 
Bibliography 
Includes bibliographical references and author index 
Notes 
English 

Print version record 
Subject 
Computer science  Mathematics  Congresses


Computer programming  Congresses


Algorithms  Congresses


Machine theory  Congresses


Informatique.


Algorithms.


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 
Ochmanski, Edward


Tyszkiewicz, Jerzy.

ISBN 
9783540852384 

3540852387 

9783540852377 

3540852379 
