Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:classical_decision_problem [2008/04/02 23:53] vkuncak |
sav08:classical_decision_problem [2008/04/03 13:34] vkuncak |
||
|---|---|---|---|
| Line 6: | Line 6: | ||
| Classify formulas according to | Classify formulas according to | ||
| + | * regular expression describing the sequence of quantifiers (e.g. $\exists^* \forall^*$ means formulas $\exists x_1. \ldots. \exists x_n. \forall y_1.\ldots \forall y_m. F$ where $F$ is quantifier-free) | ||
| + | * sequence of numbers of relation symbols for each arity | ||
| + | * sequence of numbers of function symbols for each arity | ||
| * presence or absence of equality in formulas | * presence or absence of equality in formulas | ||
| - | * regular expression describing the sequence of quantifiers (e.g. $\exists^* \forall^*$ means formulas $\forall x_1. \ldots. \forall x_n. \exists y_1.\ldots \exists y_n. F$) | ||
| - | * number and arity of relation symbols | ||
| - | * number and arity of function symbols | ||
| For each such description, determine whether the subsets of formulas that satisfy it are decidable or not. | For each such description, determine whether the subsets of formulas that satisfy it are decidable or not. | ||