Conference 
Symposium on Mathematical Foundations of Computer Science (1972 ) (34th : 2009 : Novy Smokovec, Slovakia)

Series 
Lecture notes in computer science ; 5734. 

LNCS sublibrary. SL 1, Theoretical computer science and general issues. 

Lecture notes in computer science ;
5734.


LNCS sublibrary. SL 1, Theoretical computer science and general issues.

Subject 
Computer programming  Congresses.


Algorithms  Congresses.


Computable functions  Congresses.


Machine theory  Congresses.


Artificial Intelligence.


Algorithms.


Mathematical Computing.


Software.

Alt Name 
Královič, Rastislav.


Niwiński, Damian.

Add Title 
MFCS 2009 
Description 
1 online resource (xv, 760 pages) : illustrations. 

polychrome rdacc 
Note 
Print version record. 
Bibliography Note 
Includes bibliographical references and index. 
Summary 
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, computerassisted reasoning, concurrency theory, cryptography and security, databases and knowledgebased 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. 
Contents 
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  EnergyEfficient Communication in Multiinterface Wireless Networks  Private Capacities in Mechanism Design  Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules  Sampling Edge Covers in 3Regular Graphs  Balanced Paths in Colored Graphs  Few Product Gates But Many Zeros  Branching Programs for Tree Evaluation  A Dichotomy Theorem for Polynomial Evaluation  DPComplete Problems Derived from Extremal NPComplete Properties  The Synchronization Problem for Locally Strongly Transitive Automata  Constructing Brambles  Selfindexed Text Compression Using StraightLine Programs  Security and Tradeoffs of the AklTaylor Scheme and Its Variants  Parameterized Complexity Classes under Logical Reductions  The Communication Complexity of Nonsignaling 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  FutureLooking Logics on Data Words and Trees  A ByLevel Analysis of Multiplicative Exponential Linear Logic  Hyperminimisation Made Efficient  Regular Expressions with Counting: Weak versus Strong Determinism  Choosability of P 5Free Graphs  TimeBounded 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 Nonsurjective 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 Selfgenerating Sets  The Isomorphism Problem for kTrees Is Complete for Logspace  SnakeDeterministic Tiling Systems  Query Automata for Nested Words  A General Class of Models of  The Complexity of Satisfiability for Fragments of Hybrid LogicPart I  Colouring Nonsparse 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 OneDimensional 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. 
ISBN 
9783642038167 

3642038166 

9783642038150 

3642038158 
OCLC # 
458562930 
Additional Format 
Print version: Symposium on Mathematical Foundations of Computer Science (1972 ) (34th : 2009 : Novy Smokovec, Slovakia). Mathematical foundations of computer science 2009. Berlin ; New York : Springer, 2009 9783642038150 3642038158 (OCoLC)436909826. 
