Skip to main content
SpringerLink
Log in

Computer Science - Theory and Applications

Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Edward A. Hirsch
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Alexander A. Razborov
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Alexei Semenov
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Anatol Slissenko
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5010)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: CSR 2008.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (39 papers)

  1. Front Matter

    Download chapter PDF

  2. Opening Lecture

    1. Randomness – A Computational Complexity Perspective

      • Avi Wigderson
      Pages 1-2

  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
Back to top

Other volumes

  1. Computer Science – Theory and Applications

Keywords

About this book

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.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation