Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
msol_over_strings [2007/05/08 20:32] vaibhav.rajan |
msol_over_strings [2007/05/27 12:43] vaibhav.rajan |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== MSOL over Strings ====== | ====== MSOL over Strings ====== | ||
+ | |||
+ | |||
+ | |||
===== Syntax and Semantics of Weak Monadic Second-Order Logic over Strings ===== | ===== Syntax and Semantics of Weak Monadic Second-Order Logic over Strings ===== | ||
Line 22: | Line 25: | ||
[\![v_1 \subseteq v_2]\!]e &=& (e(v_1) \subseteq e(v_2)) \\ \ | [\![v_1 \subseteq v_2]\!]e &=& (e(v_1) \subseteq e(v_2)) \\ \ | ||
[\![s(v_1,v_2)]\!]e &=& (\exists k \in N_0. e(v_1) = \{k\} \land e(v_2)=\{k+1\}) \\ \ | [\![s(v_1,v_2)]\!]e &=& (\exists k \in N_0. e(v_1) = \{k\} \land e(v_2)=\{k+1\}) \\ \ | ||
- | [\![F_1 \lor F_2]\!]e &=& [\![F_1]\!]e\ \land\ [\![F_2]\!]e \\ \ | + | [\![F_1 \lor F_2]\!]e &=& [\![F_1]\!]e\ \lor\ [\![F_2]\!]e \\ \ |
[\![\lnot F]\!]e &=& \lnot ([\![F]\!]e) \\ \ | [\![\lnot F]\!]e &=& \lnot ([\![F]\!]e) \\ \ | ||
- | [\![\exists v. F]\!] &=& \exists S \subseteq N_0. [\![F]\!](e[v \mapsto S]) | + | [\![\exists v. F]\!]e &=& \exists S. S\ \mbox{is finite}\ \land\ S \subseteq N_0 \land [\![F]\!](e[v \mapsto S]) |
\end{eqnarray*} | \end{eqnarray*} | ||
+ | |||
===== What can we express in MSOL over strings ===== | ===== What can we express in MSOL over strings ===== | ||
Line 44: | Line 48: | ||
**Transitive closure of a relation.** If $F(x,y)$ is a formula on singletons, we define reflexive transitive closure as follows. Define shorthand | **Transitive closure of a relation.** If $F(x,y)$ is a formula on singletons, we define reflexive transitive closure as follows. Define shorthand | ||
\begin{equation*} | \begin{equation*} | ||
- | \mbox{Closed}(S,R) = (\forall x,y. One(x) \land One(y) \land x \in S \land F(x,y) \rightarrow y \in S) | + | \mbox{Closed}(S,F) = (\forall x,y. One(x) \land One(y) \land x \in S \land F(x,y) \rightarrow y \in S) |
\end{equation*} | \end{equation*} | ||
Then $(u,v) \in \{(x,y) \mid F(x,y)\}^*$ is defined by | Then $(u,v) \in \{(x,y) \mid F(x,y)\}^*$ is defined by | ||
\begin{equation*} | \begin{equation*} | ||
- | \forall S. u \in S \land \mbox{Closed}(S,R) \rightarrow v \in S | + | \forall S. u \in S \land \mbox{Closed}(S,F) \rightarrow v \in S |
\end{equation*} | \end{equation*} | ||
**Using transitive closure and successors:** | **Using transitive closure and successors:** | ||
* Constant zero: $(x=0) = One(x) \land \lnot (\exists y. One(y) \land s(y,x))$ | * Constant zero: $(x=0) = One(x) \land \lnot (\exists y. One(y) \land s(y,x))$ | ||
- | * Addition by constant: $(x = y + c) = (\exists y_1,\ldots,y_{c-1}. s(y,y_1) \land s(y_1,y_2) \land \ldots \land s(y_{k-1},x))$ | + | * Addition by constant: $(x = y + c) = (\exists y_1,\ldots,y_{c-1}. s(y,y_1) \land s(y_1,y_2) \land \ldots \land s(y_{c-1},x))$ |
* Ordering on positions in the string: $(u \leq v) = ((u,v) \in \{(x,y)|s(x,y))\}^*$ | * Ordering on positions in the string: $(u \leq v) = ((u,v) \in \{(x,y)|s(x,y))\}^*$ | ||
* Reachability in $k$-increments, that is, $\exists k \geq 0. y=x + c\cdot k$: $\mbox{Reach}_c(u,v) = ((u,v) \in \{(x,y)\mid y=x+c\})$ | * Reachability in $k$-increments, that is, $\exists k \geq 0. y=x + c\cdot k$: $\mbox{Reach}_c(u,v) = ((u,v) \in \{(x,y)\mid y=x+c\})$ |