# Differences

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

 sav08:homework12 [2008/05/15 10:24]vkuncak sav08:homework12 [2015/04/21 17:30] (current) Both sides previous revision Previous revision 2008/05/15 10:24 vkuncak 2008/05/15 10:23 vkuncak 2008/05/15 10:08 vkuncak 2008/05/15 10:06 vkuncak 2008/05/15 10:05 vkuncak 2008/05/14 20:08 vkuncak 2008/05/14 20:03 vkuncak 2008/05/14 19:59 vkuncak 2008/05/14 19:59 vkuncak 2008/05/14 19:58 vkuncak created 2008/05/15 10:24 vkuncak 2008/05/15 10:23 vkuncak 2008/05/15 10:08 vkuncak 2008/05/15 10:06 vkuncak 2008/05/15 10:05 vkuncak 2008/05/14 20:08 vkuncak 2008/05/14 20:03 vkuncak 2008/05/14 19:59 vkuncak 2008/05/14 19:59 vkuncak 2008/05/14 19:58 vkuncak created 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)$.