Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
sav08:deciding_a_language_of_sets_and_relations [2009/05/20 10:57] piskac |
sav08:deciding_a_language_of_sets_and_relations [2015/04/21 17:30] (current) |
||
---|---|---|---|
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 \\ | ||
Line 10: | Line 10: | ||
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. |