Skip to main content
SpringerLink
Log in
Book cover

Computation Theory and Logic

  • Book
  • © 1987

Overview

Editors:
  1. Egon Börger
    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 270)

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 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 (37 chapters)

  1. Front Matter

    Download chapter PDF

  2. Minimal pairs for polynomial time reducibilities

    • Klaus Ambos-Spies
    Pages 1-13

  3. Primitive recursive word-functions of one variable

    • Günter Asser
    Pages 14-19

  4. Existential fixed-point logic

    • Andreas Blass, Yuri Gurevich
    Pages 20-36

  5. Unsolvable decision problems for PROLOG programs

    • Egon Börger
    Pages 37-48

  6. You have not understood a sentence, unless you can prove it

    • Hans-Jürgen Brämik
    Pages 49-58

  7. On the minimality of K, F, and D or: Why löten is non-trivial

    • Anne Brüggemann-Klein, Rolf Klein
    Pages 59-66

  8. A 5-color-extension-theorem

    • Hans-Georg Carstens
    Pages 67-77

  9. Closure relations, Buchberger's algorithm, and polynomials in infinitely many variables

    • Daniel E. Cohen
    Pages 78-87

  10. The benefit of microworlds in learning computer programming

    • E. Cohors-Fresenborg
    Pages 88-100

  11. Skolem normal forms concerning the least fixpoint

    • Elias Dahlhaus
    Pages 101-106

  12. Spectral representation of recursively enumerable and coenumerable predicates

    • M. Deutsch
    Pages 107-116

  13. Aggregating inductive expertise on partial recursive functions

    • Anne Drosdol, Britta Schinzel
    Pages 117-130

  14. Domino threads and complexity

    • H. -D. Ebbinghaus
    Pages 131-142

  15. Modelling of cooperative processes

    • Erwin Engeler
    Pages 143-153

  16. A setting for generalized computability

    • G. Germano, S. Mazzanti
    Pages 154-165

  17. First-order spectra with one variable

    • E. Grandjean
    Pages 166-180

  18. On the early history of register machines

    • G. Hasenjaeger
    Pages 181-188

  19. Randomness, provability, and the separation of Monte Carlo Time and space

    • Marek Karpinski, Rutger Verbeek
    Pages 189-207

  20. Representation independent query and update operations on propositional definite Horn formulas

    • Hans Kleine Büning, Theodor Lettmann
    Pages 208-223
Back to top

Keywords

About this book

This volume contains 37 invited research papers collected in memory of Dieter Rödding, who is known for his work on the classification of recursive functions, on reduction classes, on the spectrum problem and on the complexity of cardinality quantifiers in predicate logic and in arithmetical hierarchy. He was one of the first to pursue the interaction of logic and computer science. The volume reflects the wide spectrum of Dieter Rödding's scientific interests.

Bibliographic Information

  • Book Title: Computation Theory and Logic

  • Editors: Egon Börger

  • Series Title: Lecture Notes in Computer Science

  • DOI: https://doi.org/10.1007/3-540-18170-9

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag Berlin Heidelberg 1987

  • Softcover ISBN: 978-3-540-18170-5Published: 29 July 1987

  • eBook ISBN: 978-3-540-47795-2Published: 01 July 2005

  • Series ISSN: 0302-9743

  • Series E-ISSN: 1611-3349

  • Edition Number: 1

  • Number of Pages: IX, 442

  • Topics: Theory of Computation, Computation by Abstract Devices

Publish with us

Policies and ethics

Back to top

Search

Navigation