Lab for Automated Reasoning and Analysis 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:26]
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, 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.
  
 
regular_expressions_for_automata_with_parallel_inputs.txt · Last modified: 2015/04/21 17:32 (external edit)
 
© EPFL 2018 - Legal notice