Skip to main content
Springer Nature Link
Log in

The Computational Complexity of Logical Theories

  • Book
  • © 1979

Overview

Authors:
  1. Jeanne Ferrante
  2. Charles W. Rackoff

Part of the book series: Lecture Notes in Mathematics (LNM, volume 718)

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)

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Explore related subjects

Discover the latest articles, books and news in related subjects.

Table of contents (9 chapters)

  1. Front Matter

    Pages I-VIII
    Download chapter PDF

  2. Introduction and background

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 1-27

  3. Ehrenfeucht games and decision procedures

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 28-46

  4. Integer addition — An example of an Ehrenfeucht game decision procedure

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 47-54

  5. Some additional upper bounds

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 55-127

  6. Direct products of theories

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 128-147

  7. Lower bound preliminaries

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 148-152

  8. A technique for writing short formulas defining complicated properties

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 153-161

  9. A lower bound on the theories of pairing functions

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 162-186

  10. Some additional lower bounds

    • Jeanne Ferrante, Charles W. Rackoff
    Pages 187-233

  11. Back Matter

    Pages 234-243
    Download chapter PDF
Back to top

Accessibility Information

PDF accessibility summary

This PDF is not accessible. It is based on scanned pages and does not support features such as screen reader compatibility or descriptions for non-text content (e.g., images and graphs). However, it likely supports searchable and selectable text based on OCR (Optical Character Recognition). Users with accessibility needs may not be able to use this content effectively. Please contact us at through this accessibility request webform if you require assistance or an alternative format.

Bibliographic Information

  • Book Title: The Computational Complexity of Logical Theories

  • Authors: Jeanne Ferrante, Charles W. Rackoff

  • Series Title: Lecture Notes in Mathematics

  • DOI: https://doi.org/10.1007/BFb0062837

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag Berlin Heidelberg 1979

  • Softcover ISBN: 978-3-540-09501-9Published: 01 July 1979

  • eBook ISBN: 978-3-540-35197-9Published: 15 November 2006

  • Series ISSN: 0075-8434

  • Series E-ISSN: 1617-9692

  • Edition Number: 1

  • Number of Pages: XII, 244

  • Topics: Mathematics, general

Keywords

Publish with us

Policies and ethics

Back to top