• English only

# Differences

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

 sav08:deciding_a_language_of_sets_and_relations [2009/05/14 12:05]vkuncak sav08:deciding_a_language_of_sets_and_relations [2015/04/21 17:30] (current) Both sides previous revision Previous revision 2009/05/20 10:57 piskac 2009/05/14 12:05 vkuncak 2008/04/03 13:49 vkuncak 2008/04/03 13:45 vkuncak created Next revision Previous revision 2009/05/20 10:57 piskac 2009/05/14 12:05 vkuncak 2008/04/03 13:49 vkuncak 2008/04/03 13:45 vkuncak created Line 3: Line 3: Consider a simple language of sets: Consider a simple language of sets: - $+ \begin{equation*} \begin{array}{l} \begin{array}{l} S ::= V \mid S \cup S \mid S \cap S \mid S \setminus S \mid \mathbf{U} \mid \emptyset \\ S ::= V \mid S \cup S \mid S \cap S \mid S \setminus S \mid \mathbf{U} \mid \emptyset \\ A ::= (S = S) \mid (S \subseteq S) \mid card(S){=}c \mid card(S) \leq c \mid card(S) \geq c \\ A ::= (S = S) \mid (S \subseteq S) \mid card(S){=}c \mid card(S) \leq c \mid card(S) \geq c \\ - F ::= F \lor F \mid F \land F \mid \lnot F \\ + F ::= F \lor F \mid F \land F \mid \lnot F \mid A \\ c ::= 0 \mid 1 \mid 2 \mid ... c ::= 0 \mid 1 \mid 2 \mid ... \end{array} \end{array} -$ + \end{equation*} We show that this language is decidable by reduction to universal class. We show that this language is decidable by reduction to universal class.