E-Book, Englisch, 445 Seiten, eBook
8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013, Proceedings
E-Book, Englisch, 445 Seiten, eBook
Reihe: Theoretical Computer Science and General Issues
ISBN: 978-3-642-38536-0
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
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.
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
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-CheckingBounded Multi-Pushdown Systems.- Multi-weighted Automata and MSO Logic.- Overlapping Tile Automata.
