# Differences

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

Both sides previous revision Previous revision | |||

sav08:homework12 [2008/05/15 10:24] vkuncak |
sav08:homework12 [2015/04/21 17:30] (current) |
||
---|---|---|---|

Line 9: | Line 9: | ||

Describe the set of all binary relations $r^s_F$ definable through singleton sets | Describe the set of all binary relations $r^s_F$ definable through singleton sets | ||

- | \[ | + | \begin{equation*} |

r^s_F = \{(p,q) \mid F(\{p\},\{q\}) \} | r^s_F = \{(p,q) \mid F(\{p\},\{q\}) \} | ||

- | \] | + | \end{equation*} |

where $F$ are formulas of WS1S. How does this set of $r^s_F$ compare to the set of all binary relations definable in Presburger arithmetic | where $F$ are formulas of WS1S. How does this set of $r^s_F$ compare to the set of all binary relations definable in Presburger arithmetic | ||

- | \[ | + | \begin{equation*} |

r^p_F = \{ (p,q) \mid G(p,q) \} | r^p_F = \{ (p,q) \mid G(p,q) \} | ||

- | \] | + | \end{equation*} |

where $G$ is a Presburger arithmetic formula. Are the set of all $r^s_F$ and set of all $r^p_F$ equal, is one strict subset of the other, or are they incomparable? | where $G$ is a Presburger arithmetic formula. Are the set of all $r^s_F$ and set of all $r^p_F$ equal, is one strict subset of the other, or are they incomparable? | ||

Line 23: | Line 23: | ||

Extend the language of monadic second-order logic over strings with new predicate symbols and describe an algorithm that, given formulas $P(x,y)$ and $Q(y,z)$ in this extension (where $x$,$y$,$z$ are $n$-tuples of set variables) checks whether | Extend the language of monadic second-order logic over strings with new predicate symbols and describe an algorithm that, given formulas $P(x,y)$ and $Q(y,z)$ in this extension (where $x$,$y$,$z$ are $n$-tuples of set variables) checks whether | ||

- | \[ | + | \begin{equation*} |

\forall x,y,z. (P(x,y) \rightarrow Q(y,z)) | \forall x,y,z. (P(x,y) \rightarrow Q(y,z)) | ||

- | \] | + | \end{equation*} |

holds, and, if it holds, finds an interpolant for $P(x,y)$ and $Q(y,z)$. | holds, and, if it holds, finds an interpolant for $P(x,y)$ and $Q(y,z)$. | ||