Mathematical Foundations of Computer Science 2009

34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009, Proceedings
Herausgegeben:Královic, Rastislav; Niwinski, Damian

• Broschiertes Buch

Produktbeschreibung

The 34th International Symposium on Mathematical Foundations of Computer Science, MFCS2009,washeld in Novy Smokovec,High Tatras(Slovakia)during August 24 28, 2009. This volume contains 7 invited and 56 contributed papers presented at the symposium. The contributed papers were selected by the P- gram Committee out of a total of 148 submissions. MFCS 2009 was organized by the Slovak Society for Computer Science and the Faculty of Mathematics, Physics and Informatics of the Comenius Univ- sity in Bratislava. It wassupported by the EuropeanAssociation for Theoretical Computer Science. We acknowledge with gratitude the support of all these - stitutions. The series of MFCS symposia has a well-established tradition dating back to 1972. The aim is to encourage high-quality research in all branches of th- retical computer science, and to bring together researchers who do not usually meet at specialized conferences. The symposium is organized on a rotating - sis in Poland, Czech Republic, and Slovakia.

Produktdetails

• Theoretical Computer Science and General Issues 5734
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 12740345, 978-3-642-03815-0
• 2009
• Seitenzahl: 780
• Erscheinungstermin: 6. August 2009
• Englisch
• Abmessung: 235mm x 155mm x 42mm
• Gewicht: 1234g
• ISBN-13: 9783642038150
• ISBN-10: 3642038158
• Artikelnr.: 26899810

Inhaltsangabe

Invited Papers.- Four Subareas of the Theory of Constraints, and Their Links.- Synchronization of Regular Automata.- Stochastic Process Creation.- Stochastic Games with Finitary Objectives.- Stochastic Data Streams.- Recent Advances in Population Protocols.- How to Sort a Train.- Contributed Papers.- Arithmetic Circuits, Monomial Algebras and Finite Automata.- An Improved Approximation Bound for Spanning Star Forest and Color Saving.- Energy-Efficient Communication in Multi-interface Wireless Networks.- Private Capacities in Mechanism Design.- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules.- Sampling Edge Covers in 3-Regular Graphs.- Balanced Paths in Colored Graphs.- Few Product Gates But Many Zeros.- Branching Programs for Tree Evaluation.- A Dichotomy Theorem for Polynomial Evaluation.- DP-Complete Problems Derived from Extremal NP-Complete Properties.- The Synchronization Problem for Locally Strongly Transitive Automata.- Constructing Brambles.- Self-indexed Text Compression Using Straight-Line Programs.- Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants.- Parameterized Complexity Classes under Logical Reductions.- The Communication Complexity of Non-signaling Distributions.- How to Use Spanning Trees to Navigate in Graphs.- Representing Groups on Graphs.- Admissible Strategies in Infinite Games over Graphs.- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems.- Future-Looking Logics on Data Words and Trees.- A By-Level Analysis of Multiplicative Exponential Linear Logic.- Hyper-minimisation Made Efficient.- Regular Expressions with Counting: Weak versus Strong Determinism.- Choosability of P 5-Free Graphs.- Time-Bounded Kolmogorov Complexity and Solovay Functions.- The Longest Path Problem Is Polynomial on Interval Graphs.- Synthesis for Structure Rewriting Systems.- On the Hybrid Extension of CTL and CTL?+?.- Bounds on Non-surjective Cellular Automata.- FO Model Checking on Nested Pushdown Trees.- The Prismoid of Resources.- A Dynamic Algorithm for Reachability Games Played on Trees.- An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable.- Graph Decomposition for Improving Memoryless Periodic Exploration.- On FO 2 Quantifier Alternation over Words.- On the Recognizability of Self-generating Sets.- The Isomorphism Problem for k-Trees Is Complete for Logspace.- Snake-Deterministic Tiling Systems.- Query Automata for Nested Words.- A General Class of Models of .- The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I.- Colouring Non-sparse Random Intersection Graphs.- On the Structure of Optimal Greedy Computation (for Job Scheduling).- A Probabilistic PTAS for Shortest Common Superstring.- The Cost of Stability in Network Flow Games.- (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata.- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm.- From Parity and Payoff Games to Linear Programming.- Partial Randomness and Dimension of Recursively Enumerable Reals.- Partial Solution and Entropy.- On Pebble Automata for Data Languages with Decidable Emptiness Problem.- Size and Energy of Threshold Circuits Computing Mod Functions.- Points on Computable Curves of Computable Lengths.- The Expressive Power of Binary Submodular Functions.