Computer Science - Theory and Applications [electronic resource] : 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings / edited by Andrei A. Bulatov, Arseny M. Shur.

The Lovasz Local Lemma - A Survey -- An Improved Knapsack Solver for Column Generation -- QuickHeapsort: Modifications and Improved Analysis -- Alphabetic Minimax Trees in Linear Time -- Decidability and Enumeration for Automatic Sequences: A Survey -- Walking on Data Words -- Careful Synchronization of Partial Automata with Restricted Alphabets -- Random Generation of Deterministic Acyclic Automata Using the Recursive Method -- Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height -- A Short Tutorial on Order-Invariant First-Order Logic -- Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams -- Parameterized Resolution with Bounded Conjunction -- Lower and Upper Bounds for the Length of Joins in the Lambek Calculus -- Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP -- Towards NEXP versus BPP? -- Information Lower Bounds via Self-reducibility -- On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles -- Improving on Gutfreund, Shaltiel, and Ta-Shma's Paper "If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances" -- Amortized Communication Complexity of an Equality Predicate -- On Coloring of Sparse Graphs -- On Recognizing Words That Are Squares for the Shuffle Product -- Cyclic Shift on Prefix-Free Languages -- Weak Abelian Periodicity of Infinite Words -- Universality of Regular Realizability Problems -- Potential Functions in Strategic Games -- The Probabilistic Min Dominating Set Problem -- Dichotomy of the H-Quasi-Cover Problem -- QCSP on Partially Reflexive Cycles - The Wavy Line of Tractability -- Quantum Alternation -- Real Numbers, Chaos, and the Principle of a Bounded Density of Information -- Random Selection in Few Rounds -- One-Counter Verifiers for Decidable Languages -- More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding -- Composition with Algebra at the Background -- Model-Checking Bounded Multi-Pushdown Systems -- Multi-weighted Automata and MSO Logic -- Overlapping Tile Automata.