Skip to main content
SpringerLink
Log in
Book cover

STACS 95

12th Annual Symposium on Theoretical Aspects of Computer Science, Munich, Germany, March 2-4, 1995. Proceedings

  • Conference proceedings
  • © 1995

Overview

Editors:
  1. Ernst W. Mayr
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Claude Puech
    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 900)

Included in the following conference series:

Conference proceedings info: STACS 1995.

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

  1. Front Matter

    Download chapter PDF

  2. On the synthesis of strategies in infinite games

    • Wolfgang Thomas
    Pages 1-13

  3. Finding the maximum with linear error probabilities: a sequential analysis approach

    • Guy Louchard
    Pages 14-25

  4. Completeness and weak completeness under polynomial-size circuits

    • David W. Juedes, Jack H. Lutz
    Pages 26-37

  5. Communication complexity of key agreement on small ranges

    • Jin-Yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar
    Pages 38-49

  6. Pseudorandom generators and the frequency of simplicity

    • Yenjo Han, Lane A. Hemaspaandra
    Pages 50-59

  7. Classes of bounded counting type and their inclusion relations

    • Ulrich Hertrampf
    Pages 60-70

  8. Lower bounds for depth-three circuits with equals and mod-gates

    • Frederic Green
    Pages 71-82

  9. On realizing iterated multiplication by small depth threshold circuits

    • Matthias Krause
    Pages 83-94

  10. A random NP-complete problem for inversion of 2D cellular automata

    • Bruno Durand
    Pages 95-106

  11. On the subword equivalence problem for infinite words

    • Isabelle Fagnot
    Pages 107-118

  12. On the separators on an infinite word generated by a morphism

    • Emmanuelle Garel
    Pages 119-130

  13. Systolic tree ω-languages

    • Angelo Monti, Adriano Peron
    Pages 131-142

  14. Structural complexity of ω-automata

    • Sriram C. Krishnan, Anuj Puri, Robert K. Brayton
    Pages 143-156

  15. Algorithms explained by symmetries

    • Torsten Minkwitz
    Pages 157-167

  16. Generalized scans and tri-diagonal systems

    • Paul F. Fischer, Franco P. Preparata, John E. Savage
    Pages 168-180

  17. Two-dimensional pattern matching in linear time and small space

    • Maxime Crochemore, Leszek Gasieniec, Wojciech Rytter, Wojciech Plandowski
    Pages 181-192

  18. On-line and dynamic algorithms for shortest path problems

    • Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis
    Pages 193-204

  19. On compact representations of propositional circumscription

    • Marco Cadoli, Francesco M. Donini, Marco Schaerf
    Pages 205-216

  20. A set-theoretic translation method for (poly)modal logics

    • Giovanna D'Agostino, Angelo Montanari, Alberto Policriti
    Pages 217-228
Back to top

Other volumes

  1. STACS 95

Keywords

About this book

This book presents the proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS 95), held in Munich, Germany in March 1995.
Besides three invited talks, the book contains revised versions of 53 research papers selected from a total of 180 submissions. The contributions address all current aspects of theoretical computer science; they are organized in sections on complexity theory, automata theory, algorithms, logic, theory of parallel computing, communication theory, graph theory and databases, and computational geometry.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation