Differences

This shows you the differences between two versions of the page.

quasiequational_theory [2010/08/20 19:48]
jipsen created
quasiequational_theory [2010/08/20 19:49] (current)
jipsen
Line 1: Line 1:
=====Quasiequational theory===== =====Quasiequational theory=====
-A \emph{quasiequation} is a universal formula of the form $\phi_1 \mbox{ and } \phi_2 \mbox{ and }\cdots\mbox{ and } \phi_m\ \implies\ \phi_0$,+A \emph{quasiequation} is a universal formula of the form $\phi_1 \mbox{ and } \phi_2 \mbox{ and }\cdots\mbox{ and } \phi_m\ \Longrightarrow\ \phi_0$,
where the $\phi_i$ are atomic formulas. Note that for an algebraic language, the $\phi_i$ are simply equations. For $m=0$, a quasiequation where the $\phi_i$ are atomic formulas. Note that for an algebraic language, the $\phi_i$ are simply equations. For $m=0$, a quasiequation
is just a universal atomic formula. is just a universal atomic formula.
Line 10: Line 10:
of length $n$ (as a string) and output: "true" if the quasiequation holds in all members of the class, and "false" otherwise. 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 \emph{decidable} if there is an algorithm that solves the decision problem, otherwise it is {undecidable}.+The quasiequational theory is \emph{decidable} if there is an algorithm that solves the decision problem, otherwise it is \emph{undecidable}.
The complexity of the decision problem (if known) is one of PTIME, NPTIME, PSPACE, EXPTIME, ... 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, \emph{Completeness of calculi for axiomatically defined classes of algebras}, A complete deductive system for quasiequations is given in [A. Selman, \emph{Completeness of calculi for axiomatically defined classes of algebras},
-Algebra Universalis, \texfbf{2}, 1972, 20--32 [[http://www.ams.org/mathscinet-getitem?mr=47:1725|MRreview]].+Algebra Universalis, \textbf{2}, 1972, 20--32 [[http://www.ams.org/mathscinet-getitem?mr=47:1725|MRreview]].
Additional information on quasiequations can be found e.g. in Additional information on quasiequations can be found e.g. in
[[http://www.thoralf.uwaterloo.ca/htdocs/ualg.html|Stanley N. Burris and H.P. Sankappanavar, A Course in Universal Algebra]]. [[http://www.thoralf.uwaterloo.ca/htdocs/ualg.html|Stanley N. Burris and H.P. Sankappanavar, A Course in Universal Algebra]].