Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T02:49:42.517Z Has data issue: false hasContentIssue false

Prefix classes of Krom formulas1

Published online by Cambridge University Press:  12 March 2014

Stål O. Aanderaa
Affiliation:
Institute of Mathematics, University of Oslo, Blindern, Oslo 3, Norway
Harry R. Lewis
Affiliation:
Aiken Computation Laboratory, Harvard University, Cambridge, Massachusetts 02138

Extract

In this paper we consider decision problems for subclasses of Kr, the class of those formulas of pure quantification theory whose matrices are conjunctions of binary disjunctions of signed atomic formulas. If each of Q 1, …, Qn is an ∀ or an ∃, then let Q 1 … Qn be the class of those closed prenex formulas with prefixes of the form (Q 1 x 1)… (Qnxn ). Our results may then be stated as follows:

Theorem 1. The decision problem for satisfiability is solvable for the class ∀∃∀ ∩ Kr.

Theorem 2. The classes ∀∃∀∀ ∩ Kr and ∀∀∃∀ ∩ Kr are reduction classes for satisfiability.

Maslov [11] showed that the class ∃…∃∀…∀∃…∃ ∩ Kr is solvable, while the first author [1, Corollary 4] showed ∃∀∃∀ ∩ Kr and ∀∃∃∀ ∩ Kr to be reduction classes. Thus the only prefix subclass of Kr for which the decision problem remains open is ∀∃∀∃…∃∩ Kr.

The class ∀∃∀ ∩ Kr, though solvable, contains formulas whose only models are infinite (e.g., (∀x)(∃u)(∀y)[(Pxy ∨ Pyx) ∧ (¬ Pxy ∨ ¬Pyu)], which can be satisfied over the integers by taking P to be ≥). This is not the case for Maslov's class ∃…∃∀…∀∃…∃ ∩ Kr, which contains no formula whose only models are infinite ([2] [5]).

Theorem 1 was announced in [1, Theorem 4], but the proof sketched there is defective: Lemma 4 (p. 17) is incorrectly stated. Theorem 2 was announced in [9].

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1973

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