Computer Science -- Theory and Applications : 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010, Proceedings

by Ablayev, Farid; Mayr, Ernst W.

• ISBN13: 9783642131813
• ISBN10: 3642131816
• Format: Paperback
• Copyright: 2010-06-23
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the proceedings of the 5th International Computer Science Symposium in Russia, CSR 2010, held in Kazan, Russia, in June 2010. The 30 papers presented were carefully reviewed and selected from 62 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical computer science.

Table of Contents

Algorithms for Energy Management (Invited Talk)	p. 1
Sofic and Almost of Finite Type Tree-Shifts	p. 12
Proof-Based Design of Security Protocols	p. 25
Approximating the Minimum Length of Synchronizing Words is Hard	p. 37
Realizability of Dynamic MSC Languages	p. 48
The Max Quasi-Independent Set Problem	p. 60
Equilibria in Quantitative Reachability Games	p. 72
Quotient Complexity of Closed Languages	p. 84
Right-Sequential Functions on Infinite Words	p. 96
Kernelization (Invited Talk)	p. 107
Zigzags in Turing Machines	p. 109
Frameworks for Logically Classifying Polynomial-Time Optimisation Problems	p. 120
Validating the Knuth-Morris-Pratt Failure Function, Fast and Online	p. 132
Identical Relations in Symmetric Groups and Separating Words with Reversible Automata	p. 144
Time Optimal d-List Colouring of a Graph	p. 156
The Cantor Space as a Generic Model of Topologically Presented Knowledge	p. 169
Algorithmics - Is There Hope for a Unified Theory? (Invited Talk)	p. 181
Classifying Rankwidth k-DH-Graphs	p. 195
Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms	p. 204
A SAT Based Effective Algorithm for the Directed Hamiltonian Cycle Problem	p. 216
Balancing Bounded Treewidth Circuits	p. 228
Obtaining Online Ecological Colourings by Generalizing First-Fit	p. 240
Classical Simulation and Complexity of Quantum Computations (Invited Talk)	p. 252
Prefix-Free and Prefix-Correct Complexities with Compound Conditions	p. 259
Monotone Complexity of a Pair	p. 266
Symbolic Models for Single-Conclusion Proof Logics	p. 276
Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA	p. 288
Advancing Matrix Computations with Randomized Preprocessing	p. 303
Transfinite Sequences of Constructive Predicate Logics	p. 315
The Quantitative Analysis of User Behavior Online - Data, Models and Algorithms (Abstract of Invited Talk)	p. 327
A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem	p. 328
Complexity of Propositional Proofs (Invited Talk)	p. 340
Quantization of Random Walks: Search Algorithms and Hitting Time (Extended Abstract of Invited Talk)	p. 343
Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems (Invited Talk)	p. 344
Growth of Power-Free Languages over Large Alphabets	p. 350
A Partially Synchronizing Coloring	p. 362
An Encoding Invariant Version of Polynomial Time Computable Distributions	p. 371
Prehistoric Phenomena and Self-referentiality	p. 384
Author Index	p. 397
Table of Contents provided by Ingram. All Rights Reserved.