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.
Author(s): Susanne Albers (auth.), Farid Ablayev, Ernst W. Mayr (eds.)
Series: Lecture Notes in Computer Science 6072 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 397
Tags: Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Discrete Mathematics in Computer Science; Computation by Abstract Devices; Mathematics of Computing
Front Matter....Pages -
Algorithms for Energy Management....Pages 1-11
Sofic and Almost of Finite Type Tree-Shifts....Pages 12-24
Proof-Based Design of Security Protocols....Pages 25-36
Approximating the Minimum Length of Synchronizing Words Is Hard....Pages 37-47
Realizability of Dynamic MSC Languages....Pages 48-59
The max quasi-independent set Problem....Pages 60-71
Equilibria in Quantitative Reachability Games....Pages 72-83
Quotient Complexity of Closed Languages....Pages 84-95
Right-Sequential Functions on Infinite Words....Pages 96-106
Kernelization....Pages 107-108
Zigzags in Turing Machines....Pages 109-119
Frameworks for Logically Classifying Polynomial-Time Optimisation Problems....Pages 120-131
Validating the Knuth-Morris-Pratt Failure Function, Fast and Online....Pages 132-143
Identical Relations in Symmetric Groups and Separating Words with Reversible Automata....Pages 144-155
Time Optimal d -List Colouring of a Graph....Pages 156-168
The Cantor Space as a Generic Model of Topologically Presented Knowledge....Pages 169-180
Algorithmics – Is There Hope for a Unified Theory?....Pages 181-194
Classifying Rankwidth k -DH-Graphs....Pages 195-203
Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms....Pages 204-215
A SAT Based Effective Algorithm for the Directed Hamiltonian Cycle Problem....Pages 216-227
Balancing Bounded Treewidth Circuits....Pages 228-239
Obtaining Online Ecological Colourings by Generalizing First-Fit....Pages 240-251
Classical Simulation and Complexity of Quantum Computations....Pages 252-258
Prefix-Free and Prefix-Correct Complexities with Compound Conditions....Pages 259-265
Monotone Complexity of a Pair....Pages 266-275
Symbolic Models for Single-Conclusion Proof Logics....Pages 276-287
Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA....Pages 288-302
Advancing Matrix Computations with Randomized Preprocessing....Pages 303-314
Transfinite Sequences of Constructive Predicate Logics....Pages 315-326
The Quantitative Analysis of User Behavior Online — Data, Models and Algorithms....Pages 327-327
A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem....Pages 328-339
Complexity of Propositional Proofs....Pages 340-342
Quantization of Random Walks: Search Algorithms and Hitting Time....Pages 343-343
Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems....Pages 344-349
Growth of Power-Free Languages over Large Alphabets....Pages 350-361
A Partially Synchronizing Coloring....Pages 362-370
An Encoding Invariant Version of Polynomial Time Computable Distributions....Pages 371-383
Prehistoric Phenomena and Self-referentiality....Pages 384-396
Back Matter....Pages -
