This is an old revision of the document!

Regular Expressions and Automata with Parallel Inputs

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{array}{l}
    a_1 \\
    \ldots \\
    a_n
 \end{array}
 \right)

We can consider

regular expression
automata

on such alphabets.

Using Propositional Formulas to Denote Finite Sets of Symbols

Suppose $\Sigma = \{0,1\}$ .

Let $n=3$ .

$\Sigma^3 = \{ (0,0,0),(0,0,1),\ldots,(1,1,1) \}$ .

Language representing that the third coordinate is the logical and of the first two is: \[

\left(
\left(
 \begin{array}{l}
  0 \\
  0 \\
  0 \\
 \end{array}
 \right)
+
\left(
 \begin{array}{l}
  0 \\
  1 \\
  0 \\
 \end{array}
 \right)
+
\left(
 \begin{array}{l}
  1 \\
  0 \\
  0 \\
 \end{array}
 \right)
+
\left(
 \begin{array}{l}
  1 \\
  1 \\
  1 \\
 \end{array}
 \right)
 \right)^*

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 \[

\left(
 \begin{array}{l}
  1 \\
  1 \\
  0 \\
 \end{array}
 \right)
+
\left(
 \begin{array}{l}
  1 \\
  1 \\
  1 \\
 \end{array}
 \right)

\] The bitwise and relation, shown above, is given by \[

  [z \leftrightarrow (x \land y)]^*

In general

$\begin{equation*} [p(v_1,\ldots,v_n)] = \left( \begin{array}{l} a_{11} \\ \ldots \\ a_{1n} \end{array} \right) + \\ \ldots \\ + \\ \left( \begin{array}{l} a_{k1} \\ \ldots \\ a_{kn} \end{array} \right) \end{equation*}$

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.