Skip to main content
SpringerLink
Log in

STACS 96

13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996. Proceedings

  • Conference proceedings
  • © 1996

Overview

Editors:
  1. Claude Puech
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rüdiger Reischuk
    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 1046)

Included in the following conference series:

Conference proceedings info: STACS 1996.

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

Access this book

Log in via an institution
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 (54 papers)

  1. Front Matter

    Download chapter PDF

  2. New trends in quantum computing

    • Gilles Brassard
    Pages 1-10

  3. Compressibility and resource bounded measure

    • Harry Buhrman, Luc Longpré
    Pages 11-24

  4. On the complexity of random strings

    • Martin Kummer
    Pages 25-36

  5. Remarks on generalized Post Correspondence Problem

    • T. Harju, J. Karhumäki, D. Krob
    Pages 37-48

  6. Cyclic languages and strongly cyclic languages

    • Marie -Pierre Béal, Olivier Carton, Christophe Reutenauer
    Pages 49-59

  7. Resource-bounded balanced genericity, stochasticity and weak randomness

    • Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng
    Pages 61-74

  8. The complexity of generating and checking proofs of membership

    • Harry Buhrman, Thomas Thierauf
    Pages 75-86

  9. Observations on measure and lowness for Δ 2 P

    • Jack H. Lutz
    Pages 87-97

  10. Solvable black-box group problems are low for PP

    • V. Arvind, N. V. Vinodchandran
    Pages 99-110

  11. Languages recognized by finite aperiodic groupoids

    • Martin Beaudry
    Pages 111-124

  12. Star-height of an N-rational series

    • Frédérique Bassino
    Pages 125-135

  13. An aperiodic set of Wang cubes

    • Karel Culik II, Jarkko Kari
    Pages 137-146

  14. Lyndon factorization of infinite words

    • Guy Melançon
    Pages 147-154

  15. Embedding graphs with bounded treewidth into optimal hypercubes

    • Volker Heun, Ernst W. Mayr
    Pages 155-168

  16. Parallel comparability graph recognition and modular decomposition

    • Michel Morvan, Laurent Viennot
    Pages 169-180

  17. Fault-tolerant shared memory simulations

    • Petra Berenbrink, Friedhelm Meyer auf der Heide, Volker Stemann
    Pages 181-192

  18. On word-level parallelism in fault-tolerant computing

    • Piotr Indyk
    Pages 193-204

  19. Learning with confidence

    • Jānis Bārzdiņs, Rūsiņš Freivalds, Carl H. Smith
    Pages 205-218

  20. Extracting best consensus motifs from positive and negative examples

    • Erika Tateishi, Osamu Maruyama, Satoru Miyano
    Pages 219-230
Back to top

Other volumes

  1. STACS 96

Keywords

About this book

This book constitutes the refereed proceedings of the 13th Symposium on Theoretical Aspects of Computer Science, STACS 96, held in Grenoble, France in February 1996.
The 52 revised papers presented were selected from a total of 185 submissions; also included are three invited papers. The volume addresses all current aspects of theoretical computer science and is organized in sections on complexity theory, automata theory, parallel algorithms, learning, parallel and distributed systems, cryptography, logic and database theory, algorithms, semantics and program verification, and communication complexity.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation