Skip to main content
SpringerLink
Log in

Computer Science -- Theory and Applications

First International Symposium on Computer Science in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings

  • Conference proceedings
  • © 2006

Overview

Editors:
  1. Dima Grigoriev

    1. IRMAR, Université de Rennes, Rennes Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. John Harrison

    1. Intel Corporation, Hillsboro, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Edward A. Hirsch

    1. Steklov Institute of Mathematics at St. Petersburg, Petersburg, Russia

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

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

Included in the following conference series:

Conference proceedings info: CSR 2006.

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 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.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 (67 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Papers

    1. Non-black-box Techniques in Cryptography

      • Boaz Barak
      Pages 1-1

    2. Complexity of Polynomial Multiplication over Finite Fields

      • Michael Kaminski
      Pages 2-2

    3. Synchronous Elastic Circuits

      • Mike Kishinevsky, Jordi Cortadella, Bill Grundmann, Sava Krstić, John O’Leary
      Pages 3-5

  3. Theory Track

    1. SZK Proofs for Black-Box Group Problems

      • V. Arvind, Bireswar Das
      Pages 6-17

    2. Canonical Decomposition of a Regular Factorial Language

      • S. V. Avgustinovich, A. E. Frid
      Pages 18-22

    3. Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure

      • Maxim A. Babenko
      Pages 23-34

    4. Inductive Type Schemas as Functors

      • Freiric Barral, Sergei Soloviev
      Pages 35-45

    5. Unfolding Synthesis of Asynchronous Automata

      • Nicolas Baudru, Rémi Morin
      Pages 46-57

    6. Conjugacy and Equivalence of Weighted Automata and Functional Transducers

      • Marie-Pierre Béal, Sylvain Lombardy, Jacques Sakarovitch
      Pages 58-69

    7. Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees

      • Piotr Berman, Martin Fürer, Alexander Zelikovsky
      Pages 70-79

    8. Tuples of Disjoint NP-Sets

      • Olaf Beyersdorff
      Pages 80-91

    9. Constructive Equivalence Relations on Computable Probability Measures

      • Laurent Bienvenu
      Pages 92-103

    10. Planar Dimer Tilings

      • Olivier Bodini, Thomas Fernique
      Pages 104-113

    11. The Complexity of Equality Constraint Languages

      • Manuel Bodirsky, Jan Kára
      Pages 114-126

    12. Window Subsequence Problems for Compressed Texts

      • Patrick Cégielski, Irène Guessarian, Yury Lifshits, Yuri Matiyasevich
      Pages 127-136

    13. Efficient Algorithms in Zero-Characteristic for a New Model of Representation of Algebraic Varieties

      • Alexander L. Chistov
      Pages 137-146

    14. Relativisation Provides Natural Separations for Resolution-Based Proof Systems

      • Stefan Dantchev
      Pages 147-158

    15. Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems

      • Stefan Dantchev, Florent Madelaine
      Pages 159-170

    16. Isolation and Reducibility Properties and the Collapse Result

      • Sergey M. Dudakov
      Pages 171-177
Back to top

Other volumes

  1. Computer Science – Theory and Applications

Keywords

Editors and Affiliations

  • IRMAR, Université de Rennes, Rennes Cedex, France

    Dima Grigoriev

  • Intel Corporation, Hillsboro, USA

    John Harrison

  • Steklov Institute of Mathematics at St. Petersburg, Petersburg, Russia

    Edward A. Hirsch

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation