LARA

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
regular_expressions_for_automata_with_parallel_inputs [2009/04/28 20:25]
vkuncak
regular_expressions_for_automata_with_parallel_inputs [2015/04/21 17:32] (current)
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 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.