# Quasiequational theory

HomePage | RecentChanges | Preferences

Difference (from prior major revision) (minor diff)

Changed: 1,2c1,3
 A quasiequation is a universal formula of the form φ0  and  φ1  and  ···  and  φm−1   ⇒  φm, where the φi are atomic formulas. Note that for an algebraic language, the φi are simply equations.
 A quasiequation is a universal formula of the form φ1  and  φ2  and  ···  and  φm   ⇒  φ0, where the φi are atomic formulas. Note that for an algebraic language, the φi are simply equations. For m = 0, a quasiequation is just a universal atomic formula.

Changed: 9c10
 The equational theory is decidable if there is an algorithm that solves the decision problem, otherwise it is undecidable.
 The quasiequational theory is decidable if there is an algorithm that solves the decision problem, otherwise it is undecidable.

Changed: 13,14c14,27
 For more on quasiequations, see
 A complete deductive system for quasiequations is given in [ A. Selman, Completeness of calculi for axiomatically defined classes of algebras, Algebra Universalis 2 (1972) 20--32 MRreview ]. Additional information on quasiequations can be found e.g. in

A quasiequation is a universal formula of the form φ1  and  φ2  and  ···  and  φm   ⇒  φ0, where the φi are atomic formulas. Note that for an algebraic language, the φi are simply equations. For m = 0, a quasiequation is just a universal atomic formula.

The quasiequational theory of a class of structures is the set of quasiequations that hold in all members of the class.

The decision problem for the quasiequational theory of a class of structures is the problem with input: a quasiequation of length n (as a string) and output: "true" if the quasiequation holds in all members of the class, and "false" otherwise.

The quasiequational theory is decidable if there is an algorithm that solves the decision problem, otherwise it is undecidable.

The complexity of the decision problem (if known) is one of PTIME, NPTIME, PSPACE, EXPTIME, ...

A complete deductive system for quasiequations is given in [A. Selman, Completeness of calculi for axiomatically defined classes of algebras, Algebra Universalis 2 (1972) 20--32 MRreview]. Additional information on quasiequations can be found e.g. in [Stanley N. Burris and H.P. Sankappanavar, A Course in Universal Algebra].

HomePage | RecentChanges | Preferences