# 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]]. | ||

Trace: