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

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 -