Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:classical_decision_problem [2008/04/02 23:03] vkuncak |
sav08:classical_decision_problem [2008/04/02 23:06] vkuncak |
||
|---|---|---|---|
| Line 6: | Line 6: | ||
| Classify formulas according to | Classify formulas according to | ||
| + | * 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$) | * 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. | ||
| + | |||
| + | Example: the exists-forall class that we will study is denoted | ||
| + | |||
| + | ===== References ===== | ||
| + | |||
| * [[http://www.logic.rwth-aachen.de/pub/graedel/Gr-kalmar03.ps|Decidable Classes of First-Order and Fixpoint Logics]] | * [[http://www.logic.rwth-aachen.de/pub/graedel/Gr-kalmar03.ps|Decidable Classes of First-Order and Fixpoint Logics]] | ||
| * [[http://www.di.unipi.it/~boerger/decpblbook.html|Egon Börger, Erich Grädel, Yuri Gurevich: The Classical Decision Problem]], also on [[http://books.google.ch/books?id=3po2Tv_UVcMC&vq=On+the+classical+decision+problem|Google Books]] | * [[http://www.di.unipi.it/~boerger/decpblbook.html|Egon Börger, Erich Grädel, Yuri Gurevich: The Classical Decision Problem]], also on [[http://books.google.ch/books?id=3po2Tv_UVcMC&vq=On+the+classical+decision+problem|Google Books]] | ||