Skip to main content
SpringerLink
Log in

Computer Science - Theory and Applications

Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009, Proceedings

  • Conference proceedings
  • © 2009

Overview

Editors:
  1. Anna Frid

    1. Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Andrey Morozov

    1. Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Andrey Rybalchenko

    1. Max Planck Institute for Software Systems, Saarbrücken, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Klaus W. Wagner

    1. Lehrstuhl für Theoretische Informatik, Institut für Informatik, Julius-Maximilians-Universität Würzburg, Am Hubland, Würzburg, Germany

    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 5675)

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

Included in the following conference series:

Conference proceedings info: CSR 2009.

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 (33 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Papers

    1. Well-Founded and Partial Stable Semantics Logical Aspects

      • Pedro Cabalar, Sergei Odintsov, David Pearce
      Pages 1-11

    2. The Reachability Problem over Infinite Graphs

      • Wolfgang Thomas
      Pages 12-18

    3. Kolmogorov Complexity and Model Selection

      • Nikolay Vereshchagin
      Pages 19-24

    4. Automatic Verification of Heap-Manipulating Programs Using Separation Logic

      • Hongseok Yang
      Pages 25-25

  3. Accepted Papers

    1. Canonical Calculi: Invertibility, Axiom Expansion and (Non)-determinism

      • Arnon Avron, Agata Ciabattoni, Anna Zamansky
      Pages 26-37

    2. Integrality Property in Preemptive Parallel Machine Scheduling

      • Philippe Baptiste, Jacques Carlier, Alexander Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko
      Pages 38-46

    3. Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes

      • Olaf Beyersdorff, Zenon Sadowski
      Pages 47-58

    4. k-SAT Is No Harder Than Decision-Unique-k-SAT

      • Chris Calabro, Ramamohan Paturi
      Pages 59-70

    5. Unique Decipherability in the Monoid of Languages: An Application of Rational Relations

      • Christian Choffrut, Juhani Karhumäki
      Pages 71-79

    6. Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model

      • Yi Deng, Giovanni Di Crescenzo, Dongdai Lin, Dengguo Feng
      Pages 80-91

    7. Approximability Distance in the Space of H-Colourability Problems

      • Tommy Färnqvist, Peter Jonsson, Johan Thapper
      Pages 92-104

    8. On Random Ordering Constraints

      • Andreas Goerdt
      Pages 105-116

    9. Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

      • Kristoffer Arnsfelt Hansen
      Pages 117-128

    10. A Feebly Secure Trapdoor Function

      • Edward A. Hirsch, Sergey I. Nikolenko
      Pages 129-142

    11. Partitioning Graphs into Connected Parts

      • Pim van ’t Hof, Daniël Paulusma, Gerhard J. Woeginger
      Pages 143-154

    12. Structural Complexity of AvgBPP

      • Dmitry Itsykson
      Pages 155-166

    13. Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

      • Maurice Jansen
      Pages 167-178

    14. Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity

      • Maurice Jansen, Raghavendra Rao B.V.
      Pages 179-190

    15. One-Nonterminal Conjunctive Grammars over a Unary Alphabet

      • Artur Jeż, Alexander Okhotin
      Pages 191-202
Back to top

Other volumes

  1. Computer Science - Theory and Applications

Keywords

Editors and Affiliations

  • Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia

    Anna Frid, Andrey Morozov

  • Max Planck Institute for Software Systems, Saarbrücken, Germany

    Andrey Rybalchenko

  • Lehrstuhl für Theoretische Informatik, Institut für Informatik, Julius-Maximilians-Universität Würzburg, Am Hubland, Würzburg, Germany

    Klaus W. Wagner

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation