Differences
This shows you the differences between two versions of the page.
| Next revision Both sides next revision | |||
|
expressing_regular_expressions_in_msol_over_strings [2007/05/06 20:59] vkuncak created |
expressing_regular_expressions_in_msol_over_strings [2007/05/06 21:01] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Expressing regular expressions in MSOL over strings ====== | ====== Expressing regular expressions in MSOL over strings ====== | ||
| - | Idea: for each regular expression $r$ of alphabet with inputs $v_1,\ldots,v_n$ associate a formula $F$ with free variables $v_1,\ldots,v_n,p,q$ such that $F$ is valid precisely for whose sets of numbers for which | + | See |
| + | |||
| + | Idea: for each regular expression $r$ of a [[regular expressions for automata with parallel inputs|automaton for parallel inputs]] $v_1,\ldots,v_n$ associate a formula $F$ with free variables $v_1,\ldots,v_n,p,q$ such that $F$ is valid precisely for whose sets of numbers for which | ||
| * $p$ and $q$ are singletons | * $p$ and $q$ are singletons | ||
| * the strings given by the parts of $v_1,\ldots,v_n$ that start at position $p$ and end at position $q$ satisfy regular expression $F(r)$ | * the strings given by the parts of $v_1,\ldots,v_n$ that start at position $p$ and end at position $q$ satisfy regular expression $F(r)$ | ||