# Differences

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

 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 2007/05/06 21:04 vkuncak 2007/05/06 21:01 vkuncak 2007/05/06 21:01 vkuncak 2007/05/06 20:59 vkuncak created 2007/05/06 21:04 vkuncak 2007/05/06 21:01 vkuncak 2007/05/06 21:01 vkuncak 2007/05/06 20:59 vkuncak created Next revision Both sides next revision 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)\$