# Differences

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

 regular_expressions_for_automata_with_parallel_inputs [2009/04/28 20:26]vkuncak regular_expressions_for_automata_with_parallel_inputs [2015/04/21 17:32] (current) Both sides previous revision Previous revision 2009/04/28 20:27 vkuncak 2009/04/28 20:26 vkuncak 2009/04/28 20:25 vkuncak 2009/04/28 20:24 vkuncak 2009/04/28 20:24 vkuncak 2009/04/28 20:24 vkuncak 2009/04/28 20:23 vkuncak 2009/04/28 20:22 vkuncak 2009/04/28 20:14 vkuncak 2009/04/28 20:13 vkuncak 2008/05/14 10:50 vkuncak 2008/05/14 10:48 vkuncak 2008/05/14 10:47 vkuncak 2008/05/14 10:44 vkuncak 2008/05/14 10:43 vkuncak 2008/05/14 10:42 vkuncak 2008/05/14 10:27 vkuncak 2007/05/16 00:03 vkuncak 2007/05/15 21:35 vkuncak 2007/05/14 15:44 vkuncak 2007/05/06 19:57 vkuncak 2007/05/06 19:57 vkuncak 2007/05/06 19:47 vkuncak 2007/05/06 19:42 vkuncak 2007/05/06 19:37 vkuncak 2007/05/06 19:36 vkuncak 2007/05/06 19:31 vkuncak Next revision Previous revision 2009/04/28 20:27 vkuncak 2009/04/28 20:26 vkuncak 2009/04/28 20:25 vkuncak 2009/04/28 20:24 vkuncak 2009/04/28 20:24 vkuncak 2009/04/28 20:24 vkuncak 2009/04/28 20:23 vkuncak 2009/04/28 20:22 vkuncak 2009/04/28 20:14 vkuncak 2009/04/28 20:13 vkuncak 2008/05/14 10:50 vkuncak 2008/05/14 10:48 vkuncak 2008/05/14 10:47 vkuncak 2008/05/14 10:44 vkuncak 2008/05/14 10:43 vkuncak 2008/05/14 10:42 vkuncak 2008/05/14 10:27 vkuncak 2007/05/16 00:03 vkuncak 2007/05/15 21:35 vkuncak 2007/05/14 15:44 vkuncak 2007/05/06 19:57 vkuncak 2007/05/06 19:57 vkuncak 2007/05/06 19:47 vkuncak 2007/05/06 19:42 vkuncak 2007/05/06 19:37 vkuncak 2007/05/06 19:36 vkuncak 2007/05/06 19:31 vkuncak 2007/05/06 19:31 vkuncak 2007/05/06 19:30 vkuncak 2007/05/06 19:08 vkuncak created Line 2: Line 2: Given an alphabet $\Sigma$, we consider a larger (but still finite) alphabet $\Sigma^n$ for some $n$.  Keep in mind that $(a_1,​\ldots,​a_n) \in \Sigma_n$ is just one symbol; we often write it as Given an alphabet $\Sigma$, we consider a larger (but still finite) alphabet $\Sigma^n$ for some $n$.  Keep in mind that $(a_1,​\ldots,​a_n) \in \Sigma_n$ is just one symbol; we often write it as - $\left( + \begin{equation*}\left( ​\begin{array}{l} ​\begin{array}{l} a_1 \\ a_1 \\ Line 9: Line 9: ​\end{array} ​\end{array} ​\right) ​\right) -$ + \end{equation*} We can consider We can consider Line 15: Line 15: * automata * automata on such alphabets. on such alphabets. + ====== Using Propositional Formulas to Denote Finite Sets of Symbols ====== ====== Using Propositional Formulas to Denote Finite Sets of Symbols ====== Line 25: Line 26: Language representing that the third coordinate is the logical **and** of the first two is: Language representing that the third coordinate is the logical **and** of the first two is: - $+ \begin{equation*} \left( \left( \left( \left( Line 59: Line 60: ​\right) ​\right) ​\right)^* ​\right)^* -$ + \end{equation*} Instead of considering $\Sigma^3$, we can consider $\{x,y,z\} \to \Sigma$ where $x,y,z$ are three names of variables. Instead of considering $\Sigma^3$, we can consider $\{x,y,z\} \to \Sigma$ where $x,y,z$ are three names of variables. We then use propositional formulas to denote possible values of bits. For example, $[x \land y]$ denotes the regular expression ​ We then use propositional formulas to denote possible values of bits. For example, $[x \land y]$ denotes the regular expression ​ - $+ \begin{equation*} \left( \left( ​\begin{array}{l} ​\begin{array}{l} Line 80: Line 81: ​\end{array} ​\end{array} ​\right) ​\right) -$ + \end{equation*} The bitwise **and** relation, shown above, is given by The bitwise **and** relation, shown above, is given by - $+ \begin{equation*} [z \leftrightarrow (x \land y)]^* [z \leftrightarrow (x \land y)]^* -$ + \end{equation*} In general In general Line 109: Line 110: where $p(v_1,​\ldots,​v_n)$ is a propositional formula and $(a_{i1},​\ldots,​a_{in})$ for $1 \leq i \leq k$ are all tuples of values of propositional variables for which $p(v_1,​\ldots,​v_n)$ is true. where $p(v_1,​\ldots,​v_n)$ is a propositional formula and $(a_{i1},​\ldots,​a_{in})$ for $1 \leq i \leq k$ are all tuples of values of propositional variables for which $p(v_1,​\ldots,​v_n)$ is true. - Notational advantage: the set of variables ​can be larger, the expression ​is still the same. + Notational advantage: ​even if we increase ​the number ​of components by adding new variables, the expression ​remains ​the same.