| Description |
1 online resource (xii, 443 pages) : illustrations |
| Series |
Lecture notes in computer science, 1611-3349 ; 7913 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 7913. 1611-3349
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues
|
| Contents |
Opening Lecture. The Lovász Local Lemma -- A Survey / Mario Szegedy -- Session 1: Algorithms. An Improved Knapsack Solver for Column Generation / Klaus Jansen, Stefan Kraft -- QuickHeapsort: Modifications and Improved Analysis / Volker Diekert, Armin Weiß -- Alphabetic Minimax Trees in Linear Time / Paweł Gawrychowski -- Invited Lecture 1. Decidability and Enumeration for Automatic Sequences: A Survey / Jeffrey Shallit -- Session 2: Automata. Walking on Data Words / Amaldev Manuel, Anca Muscholl, Gabriele Puppis -- Careful Synchronization of Partial Automata with Restricted Alphabets / Pavel V. Martyugin -- Random Generation of Deterministic Acyclic Automata Using the Recursive Method / Sven De Felice, Cyril Nicaud -- Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height / Viliam Geffert, Zuzana Bednárová, Carlo Mereghetti, Beatrice Palano |
|
Invited Lecture 2. A Short Tutorial on Order-Invariant First-Order Logic / Nicole Schweikardt -- Session 3: Logic, Proof Complexity. Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams / Luke Friedman, Yixin Xu -- Parameterized Resolution with Bounded Conjunction / Stefan Dantchev, Barnaby Martin -- Lower and Upper Bounds for the Length of Joins in the Lambek Calculus / Alexey Sorokin -- Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP / Dmitry Itsykson, Vsevolod Oparin -- Invited Lecture 3. Towards NEXP versus BPP? / Ryan Williams -- Session 4: Complexity 1. Information Lower Bounds via Self-reducibility / Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein -- On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles / Anton Makhlin |
|
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" / Nikolay Vereshchagin -- Amortized Communication Complexity of an Equality Predicate / Vladimir Nikishkin -- Invited Lecture 4. On Coloring of Sparse Graphs / Alexandr Kostochka, Matthew Yancey -- Session 5: Words and Languages. On Recognizing Words That Are Squares for the Shuffle Product / Romeo Rizzi, Stéphane Vialette -- Cyclic Shift on Prefix-Free Languages / Jozef Jirásek, Galina Jirásková -- Weak Abelian Periodicity of Infinite Words / Sergey Avgustinovich, Svetlana Puzynina -- Universality of Regular Realizability Problems / Mikhail N. Vyalyi -- Invited Lecture 5. Potential Functions in Strategic Games / Paul G. Spirakis, Panagiota N. Panagopoulou -- Session 6: Algorithms 2. The Probabilistic Min Dominating Set Problem / Nicolas Boria, Cécile Murat, Vangelis Th. Paschos |
|
Dichotomy of the H-Quasi-Cover Problem / Jiří. Fiala, Marek Tesař -- QCSP on Partially Reflexive Cycles -- The Wavy Line of Tractability / Florent Madelaine, Barnaby Martin -- Quantum Alternation / Abuzer Yakaryılmaz -- Invited Lecture 6. Real Numbers, Chaos, and the Principle of a Bounded Density of Information / Gilles Dowek -- Session 7: Complexity 2. Random Selection in Few Rounds / Timofey Stepanov -- One-Counter Verifiers for Decidable Languages / Abuzer Yakaryılmaz -- More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding / Andreas Fröhlich, Gergely Kovásznai, Armin Biere -- Invited Lecture 7. Composition with Algebra at the Background / Thomas Colcombet -- Session 8: Logic, Automata. Model-Checking Bounded Multi-Pushdown Systems / Kshitij Bansal, Stéphane Demri -- Multi-weighted Automata and MSO Logic / Manfred Droste, Vitaly Perevoshchikov -- Overlapping Tile Automata / David Janin |
| 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 |
| Analysis |
computerwetenschappen |
|
computer sciences |
|
wiskunde |
|
mathematics |
|
algoritmen |
|
algorithms |
|
computeranalyse |
|
computer analysis |
|
logica |
|
logic |
|
computational science |
|
Information and Communication Technology (General) |
|
Informatie- en communicatietechnologie (algemeen) |
| Bibliography |
Includes bibliographical references and author index |
| Notes |
Online resource; title from PDF title page (SpringerLink, viewed July 23, 2013) |
| Subject |
Computer science -- Mathematics -- Congresses
|
|
Mathematics.
|
|
Artificial intelligence.
|
|
Mathematics
|
|
Artificial Intelligence
|
|
artificial intelligence.
|
|
Mathematics
|
|
Artificial intelligence
|
|
Computer science -- Mathematics
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Bulatov, Andrei A
|
|
Shur, A. M. (Arseniĭ Mikhaĭlovich)
|
| ISBN |
9783642385360 |
|
3642385362 |
|
3642385354 |
|
9783642385353 |
|
