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

Format:

Book

Contributor:

Bulatov, Andrei A., editor.

Shur, Arseny M., editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

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

Theoretical Computer Science and General Issues ; 7913

Language:

English

Subjects (All):

Algorithms.

Computer logic.

Computers.

Computer science--Mathematics.

Computer science.

Logic, Symbolic and mathematical.

Algorithm Analysis and Problem Complexity.

Logics and Meanings of Programs.

Computation by Abstract Devices.

Discrete Mathematics in Computer Science.

Mathematical Logic and Formal Languages.

Local Subjects:

Algorithm Analysis and Problem Complexity.

Logics and Meanings of Programs.

Computation by Abstract Devices.

Discrete Mathematics in Computer Science.

Mathematical Logic and Formal Languages.

Physical Description:

1 online resource (XII, 445 pages) : 55 illustrations.

Edition:

First edition 2013.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2013.

System Details:

text file PDF

Summary:

This book constitutes the proceedings of the 8th International Computer Science Symposium in Russia, CSR 2013, held in Ekaterinburg, Russia, in June 2013. The 29 full papers presented in this volume were carefully reviewed and selected from 52 submissions. In addition the book contains 8 invited lectures. The papers are organized in topical sections on: algorithms; automata; logic and proof complexity; complexity; words and languages; and logic and automata.

Contents:

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.

Other Format:

Printed edition:

ISBN:

978-3-642-38536-0

9783642385360

Access Restriction:

Restricted for use by site license.