Computer Science - Theory and Applications

1. Front Matter

   PDF

2. Opening Lecture

   1. Randomness – A Computational Complexity Perspective

      • Avi Wigderson

      Pages 1-2

3. Invited Papers

   1. Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds

      • Eric Allender

      Pages 3-10

   2. On Formal Equivalence Verification of Hardware

      • Zurab Khasidashvili

      Pages 11-12

   3. Twelve Problems in Proof Complexity

      • Pavel Pudlák

      Pages 13-27

   4. Manifestation and Exploitation of Invariants in Bioinformatics

      • Limsoon Wong

      Pages 28-28

   5. Simple Stochastic Games, Mean Payoff Games, Parity Games

      • Uri Zwick

      Pages 29-29

4. Theory Track

   1. Topological Semantics of Justification Logic

      • Sergei Artemov, Elena Nogina

      Pages 30-39

   2. A Logspace Algorithm for Partial 2-Tree Canonization

      • Vikraman Arvind, Bireswar Das, Johannes Köbler

      Pages 40-51

   3. A Triple Correspondence in Canonical Calculi: Strong Cut-Elimination, Coherence, and Non-deterministic Semantics

      • Arnon Avron, Anna Zamansky

      Pages 52-63

   4. Computing Longest Common Substrings Via Suffix Arrays

      • Maxim A. Babenko, Tatiana A. Starikovskaya

      Pages 64-75

   5. Logic and Rational Languages of Words Indexed by Linear Orderings

      • Nicolas Bedon, Alexis Bès, Olivier Carton, Chloé Rispal

      Pages 76-85

   6. Complexity of the Bollobás-Riordan Polynomial

      • Markus Bläser, Holger Dell, Johann A. Makowsky

      Pages 86-98

   7. A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames

      • Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino, Vladimir Oudalov

      Pages 99-109

   8. Synchronization of Grammars

      • Didier Caucal, Stéphane Hassen

      Pages 110-121

   9. Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates

      • Dmitriy Yu. Cherukhin

      Pages 122-133

   10. A Semantic Proof of Polytime Soundness of Light Affine Logic

       • Ugo Dal Lago, Martin Hofmann

       Pages 134-145

   11. On Subword Complexity of Morphic Sequences

       • Rostislav Deviatov

       Pages 146-157

   12. Comparing Universal Covers in Polynomial Time

       • Jiří Fiala, Daniël Paulusma

       Pages 158-167

   13. S4LP and Local Realizability

       • Melvin Fitting

       Pages 168-179

This book constitutes the refereed proceedings of the Third International Computer Science Symposium in Russia, CSR 2008, held in Moscow, Russia, June 7-12, 2008. The 33 revised papers presented together with 5 invited papers and one opening lecture were carefully reviewed and selected from 103 submissions. All major areas in computer science are addressed. The theory track deals with algorithms, protocols, and data structures; complexity and cryptography; formal languages, automata and their applications to computer science; computational models and concepts; proof theory and applications of logic to computer science. The application part comprises programming and languages; computer architecture and hardware design; symbolic computing and numerical applications; application software; artificial intelligence and robotics.

• Automat
• Hardware
• algorithms
• artificial intelligence
• automata
• complexity
• computer architecture
• computer science
• data structure
• data structures
• formal language
• programming
• proof theory
• robot
• robotics
• algorithm analysis and problem complexity

Policies and ethics