Differences

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

quasiequational_theory [2010/08/20 19:49]
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, ...