# Differences

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

quasiequational_theory [2010/08/20 19:48] jipsen |
quasiequational_theory [2010/08/20 19:49] (current) jipsen |
||
---|---|---|---|

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: