Hostname: page-component-7b7567c8c-m6dxt Total loading time: 0 Render date: 2026-11-19T03:49:32.431Z Has data issue: false hasContentIssue false

Conservative reduction classes of Krom formulas1

Published online by Cambridge University Press:  12 March 2014

Stål O. Aanderaa
Affiliation:
University of Oslo, Blindern, Oslo 3, Norway
Egon Börger
Affiliation:
Universität Dortmund, 46 Dortmund 50, Federal Republic of, Germany
Harry R. Lewis
Affiliation:
Harvard University, Cambridge, Massachusetts 02138

Abstract

A Krom formula of pure quantification theory is a formula in conjunctive normal form such that each conjunct is a disjunction of at most two atomic formulas or negations of atomic formulas. Every class of Krom formulas that is determined by the form of their quantifier prefixes and which is known to have an unsolvable decision problem for satisfiability is here shown to be a conservative reduction class. Therefore both the general satisfiability problem, and the problem of satisfiability in finite models, can be effectively reduced from arbitrary formulas to Krom formulas of these several prefix types.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1982

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable