Notice bibliographique
- Notice
Type(s) de contenu et mode(s) de consultation : Texte noté : électronique
Auteur(s) : International Computer Science Symposium in Russia (8 ; 2013 ; Ekaterinburg, Russia)
Titre(s) : Computer science--theory and applications [Texte électronique] : 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013 : proceedings / Andrei A. Bulatov, Arseny M. Shur (eds.)
Publication : Berlin : Springer, cop. 2013
Description matérielle : 1 online resource (xii, 443 pages)
Collection : Lecture notes in computer science ; 7913
LNCS sublibrary. SL 1, Theoretical computer science and general issues
Note(s) : Includes bibliographical references and author index. - Online resource; title from PDF title page (SpringerLink, viewed July 23, 2013).
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
Autre(s) auteur(s) : Bulatov, Andrei A.. Fonction indéterminée
Shur, Arseniĭ Mikhaĭlovich. Fonction indéterminée
Autre(s) forme(s) du titre :
- Autre forme du titre : CSR 2013
Sujet(s) : Informatique -- Mathématiques
Mathématiques
Intelligence artificielle
Indice(s) Dewey :
004 (23e éd.) = Informatique ; 005.1 (23e éd.) = Développement de logiciels
Identifiants, prix et caractéristiques : ISBN 9783642385360
Identifiant de la notice : ark:/12148/cb447071993
Notice n° :
FRBNF44707199
(notice reprise d'un réservoir extérieur)
Table des matières : 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