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:solving_set_constraints_using_monadic_class [2008/05/22 13:13] vkuncak |
sav08:solving_set_constraints_using_monadic_class [2008/05/22 13:16] vkuncak |
||
---|---|---|---|
Line 3: | Line 3: | ||
===== Definition of Monadic Class of FOL ===== | ===== Definition of Monadic Class of FOL ===== | ||
- | First-order logic formulas in the language that contains only unary predicates. | + | **Definition:** The class of first-order logic formulas in the language that contains only unary predicates. |
Decidability: special case of first-order theory of Boolean Algebras, or WS1S, so it can be decided using techniques we have seen: | Decidability: special case of first-order theory of Boolean Algebras, or WS1S, so it can be decided using techniques we have seen: |