Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
expressing_finite_automata_in_msol_over_strings [2010/05/21 02:31] vkuncak |
expressing_finite_automata_in_msol_over_strings [2012/05/15 12:43] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Expressing finite automaton in MSOL over strings ====== | + | ====== Expressing finite automaton in WS1S ====== |
| Consider a finite automaton with alphabet $\Sigma=\{0,1\}^n$, states $Q = \{q_0,q_1,\ldots,q_m\}$, transition relation $\Delta$, initial state $q_0$ and final states $F$. | Consider a finite automaton with alphabet $\Sigma=\{0,1\}^n$, states $Q = \{q_0,q_1,\ldots,q_m\}$, transition relation $\Delta$, initial state $q_0$ and final states $F$. | ||