product iamge

Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

This book constitutes the refereed proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science, MFCS 2009, held in Novy Smokovec, High Tatras, Slovakia, in August 2009.

The 56 revised full papers presented together with 7 invited lectures were carefully reviewed and selected from 148 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, including algorithmic game theory, algorithmic tearning theory, algorithms and data structures, automata, grammars and formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, cryptography and security, databases and knowledge-based systems, formal specifications and program development, foundations of computing, logic in computer science, mobile computing, models of computation, networks, parallel and distributed computing, quantum computing, semantics and verification of programs, theoretical issues in artificial intelligence.

Author(s): Albert Atserias (auth.), Rastislav Královič, Damian Niwiński (eds.)
Series: Lecture Notes in Computer Science 5734 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009

Language: English
Pages: 760
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Mathematics of Computing; Data Structures

Front Matter....Pages -
Four Subareas of the Theory of Constraints, and Their Links....Pages 1-1
Synchronization of Regular Automata....Pages 2-23
Stochastic Process Creation....Pages 24-33
Stochastic Games with Finitary Objectives....Pages 34-54
Stochastic Data Streams....Pages 55-55
Recent Advances in Population Protocols....Pages 56-76
How to Sort a Train....Pages 77-77
Arithmetic Circuits, Monomial Algebras and Finite Automata....Pages 78-89
An Improved Approximation Bound for Spanning Star Forest and Color Saving....Pages 90-101
Energy-Efficient Communication in Multi-interface Wireless Networks....Pages 102-111
Private Capacities in Mechanism Design....Pages 112-123
Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules....Pages 124-136
Sampling Edge Covers in 3-Regular Graphs....Pages 137-148
Balanced Paths in Colored Graphs....Pages 149-161
Few Product Gates But Many Zeros....Pages 162-174
Branching Programs for Tree Evaluation....Pages 175-186
A Dichotomy Theorem for Polynomial Evaluation....Pages 187-198
DP-Complete Problems Derived from Extremal NP-Complete Properties....Pages 199-210
The Synchronization Problem for Locally Strongly Transitive Automata....Pages 211-222
Constructing Brambles....Pages 223-234
Self-indexed Text Compression Using Straight-Line Programs....Pages 235-246
Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants....Pages 247-257
Parameterized Complexity Classes under Logical Reductions....Pages 258-269
The Communication Complexity of Non-signaling Distributions....Pages 270-281
How to Use Spanning Trees to Navigate in Graphs....Pages 282-294
Representing Groups on Graphs....Pages 295-306
Admissible Strategies in Infinite Games over Graphs....Pages 307-318
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems....Pages 319-330
Future-Looking Logics on Data Words and Trees....Pages 331-343
A By-Level Analysis of Multiplicative Exponential Linear Logic....Pages 344-355
Hyper-minimisation Made Efficient....Pages 356-368
Regular Expressions with Counting: Weak versus Strong Determinism....Pages 369-381
Choosability of P 5 -Free Graphs....Pages 382-391
Time-Bounded Kolmogorov Complexity and Solovay Functions....Pages 392-402
The Longest Path Problem Is Polynomial on Interval Graphs....Pages 403-414
Synthesis for Structure Rewriting Systems....Pages 415-426
On the Hybrid Extension of CTL and CTL  +  ....Pages 427-438
Bounds on Non-surjective Cellular Automata....Pages 439-450
FO Model Checking on Nested Pushdown Trees....Pages 451-463
The Prismoid of Resources....Pages 464-476
A Dynamic Algorithm for Reachability Games Played on Trees....Pages 477-488
An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable....Pages 489-500
Graph Decomposition for Improving Memoryless Periodic Exploration....Pages 501-512
On FO 2 Quantifier Alternation over Words....Pages 513-524
On the Recognizability of Self-generating Sets....Pages 525-536
The Isomorphism Problem for k -Trees Is Complete for Logspace....Pages 537-548
Snake-Deterministic Tiling Systems....Pages 549-560
Query Automata for Nested Words....Pages 561-573
A General Class of Models of $\mathcal{H}^*$ ....Pages 574-586
The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I....Pages 587-599
Colouring Non-sparse Random Intersection Graphs....Pages 600-611
On the Structure of Optimal Greedy Computation (for Job Scheduling)....Pages 612-623
A Probabilistic PTAS for Shortest Common Superstring....Pages 624-635
The Cost of Stability in Network Flow Games....Pages 636-650
(Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata....Pages 651-662
Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm....Pages 663-674
From Parity and Payoff Games to Linear Programming....Pages 675-686
Partial Randomness and Dimension of Recursively Enumerable Reals....Pages 687-699
Partial Solution and Entropy....Pages 700-711
On Pebble Automata for Data Languages with Decidable Emptiness Problem....Pages 712-723
Size and Energy of Threshold Circuits Computing Mod Functions....Pages 724-735
Points on Computable Curves of Computable Lengths....Pages 736-743
The Expressive Power of Binary Submodular Functions....Pages 744-757
Back Matter....Pages -