Mathematical Foundations of Computer Science 2008
Springer Berlin (Verlag)
978-3-540-85237-7 (ISBN)
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 Straight-Line Program for Computing Linear Forms.- Flip Algorithm for Segment Triangulations.- Computing Sharp 2-Factors in Claw-Free Graphs.- A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem.- Positional Strategies for Higher-Order Pushdown Parity Games.- Arthur and Merlin as Oracles.- A Decision Problem for Ultimately Periodic Sets in Non-standard 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 Apex-Minor-Free Graphs.- Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.- Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control.- Reversal-Bounded 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 k-Colorability of P 5-Free 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.- Step-Out 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 Process-Based 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 Max-2-SAT: A Graph-Theoretic 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.
Erscheint lt. Verlag | 12.8.2008 |
---|---|
Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
Zusatzinfo | XIV, 626 p. |
Verlagsort | Berlin |
Sprache | englisch |
Maße | 155 x 235 mm |
Gewicht | 959 g |
Themenwelt | Mathematik / Informatik ► Informatik |
Schlagworte | Algorithm analysis and problem complexity • Algorithmics • algorithms • approximation algorithms • arithmetical circuits • Artificial Intelligence • Attractors • Automat • Automata • Bioinformatics • Boolean functions • Cellular Automata • circuit classes • circuit complexity • Circuit theory • combinatorial optimizaion • Complexity • Complexity theory • compression • Computational Complexity • Computer Science • cryptographic proofs • data structure • data structures • Distributed Computing • Dynamical Systems • formal language • Formal Languages • formal specification • Game Theory • Graph Algorithms • graph coloring • Graph Computations • haplotyping • Hardcover, Softcover / Informatik, EDV/Informatik • HC/Informatik, EDV/Informatik • hereditary classes • Lambda Calculus • multilinear polynomials • permutative reductions • Petri Nets • picture grammar • picture language • Planar Graphs • Quantum Computing • Semantics • Symmetric functions • syntactic pattern recognition • theoretical computer science • theory of computing • verification |
ISBN-10 | 3-540-85237-9 / 3540852379 |
ISBN-13 | 978-3-540-85237-7 / 9783540852377 |
Zustand | Neuware |
Haben Sie eine Frage zum Produkt? |
aus dem Bereich