# Differences

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

Both sides previous revision Previous revision | Last revision Both sides next revision | ||

expressing_regular_expressions_in_msol_over_strings [2007/05/06 21:01] vkuncak |
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 ====== | ||

- | |||

- | 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 | 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 |