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

Trace: