Skip to main content
SpringerLink
Log in

Advances in Algorithms, Languages, and Complexity

  • Book
  • © 1997

Overview

Editors:
  1. Ding-Zhu Du

    1. University of Minnesota, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Ker-I Ko

    1. State University of New York, Stony Brook, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

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 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 219.99
Price excludes VAT (USA)
  • Durable hardcover 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 (16 chapters)

  1. Front Matter

    Pages i-xxxiv
    Download chapter PDF

  2. Theorem Proving in Hierarchical Clausal Specifications

    • J. Avenhaus, K. Madlener
    Pages 1-51

  3. Algorithms for Learning Finite Automata from Queries: A Unified View

    • José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe
    Pages 53-72

  4. Coding Complexity: The Computational Complexity of Succinct Descriptions

    • José L. Balcázar, Ricard Gavaldà, Osamu Watanabe
    Pages 73-91

  5. Homomorphic Representations of Certain Classes of Languages

    • Franz J. Brandenburg
    Pages 93-110

  6. Block-Synchronization Context-Free Grammars

    • Helmut Jürgensen, Kai Salomaa
    Pages 111-137

  7. High Sets for NP

    • Johannes Köbler, Uwe Schöning
    Pages 139-156

  8. Average-Case Analysis Using Kolmogorov Complexity

    • Ming Li, Paul Vitányi
    Pages 157-169

  9. Genericity and Randomness over Feasible Probability Measures

    • Amy K. Lorentz, Jack H. Lutz
    Pages 171-187

  10. Book’s Impact on the Theory of Thue Systems — Abstract

    • Robert McNaughton
    Pages 189-190

  11. Sparse Hard Sets for P

    • Dieter van Melkebeek, Mitsunori Ogihara
    Pages 191-208

  12. A Survey of Continuous-Time Computation Theory

    • Pekka Orponen
    Pages 209-224

  13. Properties of Monoids That Are Presented by Finite Convergent String-Rewriting Systems — A Survey

    • F. Otto, Y. Kobayashi
    Pages 225-266

  14. Relaxed Balancing in Search Trees

    • Eljas Soisalon-Soininen, Peter Widmayer
    Pages 267-283

  15. Measure One Results in Computational Complexity Theory

    • Heribert Vollmer, Klaus W. Wagner
    Pages 285-312

  16. Average-Case Intractable NP Problems

    • Jie Wang
    Pages 313-378

  17. Multichannel Lightwave Networks

    • Peng-Jun Wan, Feng Cao
    Pages 379-396
Back to top

Keywords

About this book

This book contains a collection of survey papers in the areas of algorithms, lan­ guages and complexity, the three areas in which Professor Ronald V. Book has made significant contributions. As a fonner student and a co-author who have been influenced by him directly, we would like to dedicate this book to Professor Ronald V. Book to honor and celebrate his sixtieth birthday. Professor Book initiated his brilliant academic career in 1958, graduating from Grinnell College with a Bachelor of Arts degree. He obtained a Master of Arts in Teaching degree in 1960 and a Master of Arts degree in 1964 both from Wesleyan University, and a Doctor of Philosophy degree from Harvard University in 1969, under the guidance of Professor Sheila A. Greibach. Professor Book's research in discrete mathematics and theoretical com­ puter science is reflected in more than 150 scientific publications. These works have made a strong impact on the development of several areas of theoretical computer science. A more detailed summary of his scientific research appears in this volume separately.

Editors and Affiliations

  • University of Minnesota, USA

    Ding-Zhu Du

  • State University of New York, Stony Brook, USA

    Ker-I Ko

Bibliographic Information

  • Book Title: Advances in Algorithms, Languages, and Complexity

  • Editors: Ding-Zhu Du, Ker-I Ko

  • DOI: https://doi.org/10.1007/978-1-4613-3394-4

  • Publisher: Springer New York, NY

  • eBook Packages: Springer Book Archive

  • Copyright Information: Kluwer Academic Publishers 1997

  • Hardcover ISBN: 978-0-7923-4396-7Published: 28 February 1997

  • Softcover ISBN: 978-1-4613-3396-8Published: 12 October 2011

  • eBook ISBN: 978-1-4613-3394-4Published: 01 December 2013

  • Edition Number: 1

  • Number of Pages: XXXIV, 396

  • Topics: Algorithms, Theory of Computation, Group Theory and Generalizations

Publish with us

Policies and ethics

Back to top

Search

Navigation