The Computational Complexity of Logical Theories

1979/01/01 by Jeanne Ferrante, Charles Rackoff, Charles W. Rackoff · 7 citations
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #Logic, Reasoning, and Knowledge

paper · doi:10.1007/bfb0062837

crossref issued 1979/01/01 · crossref published 1979/01/01 · crossref published-print 1979/01/01 · openalex publication_date 1979/01/01 · crossref created 2006/11/23 · crossref deposited 2019/04/06 · openalex created_date 2025/10/10 · crossref indexed 2026/06/10 · openalex updated_date 2026/07/02

Cited by

• PRESBURGER ARITHMETIC, RATIONAL GENERATING FUNCTIONS, AND QUASI-POLYNOMIALS
• Dominoes and the complexity of subclasses of logical theories
• Structural subtyping of non-recursive types is decidable
• Constraint databases: A survey
• Queries with arithmetical constraints
• The theory of hereditarily bounded sets
• Presburger arithmetic [wikipedia]
• Skolem arithmetic [wikipedia]