††thanks: Research supported by US Office of Naval Research Grant
N000141712622.

# Better Automata through Process Algebra

Rance Cleaveland  Department of Computer Science, University of Maryland,
College Park MD 20742 USA<EMAIL_ADDRESS>
###### Abstract

This paper shows how the use of Structural Operational Semantics (SOS) in the
style popularized by the process-algebra community can lead to a more succinct
and useful construction for building finite automata from regular expressions.
Such constructions have been known for decades, and form the basis for the
proofs of one direction of Kleene’s Theorem. The purpose of the new
construction is, on the one hand, to show students how small automata can be
constructed, without the need for empty transitions, and on the other hand to
show how the construction method admits closure proofs of regular languages
with respect to other operators as well. These results, while not
theoretically surprising, point to an additional influence of process-
algebraic research: in addition to providing fundamental insights into the
nature of concurrent computation, it also sheds new light on old, well-known
constructions in automata theory.

###### keywords:

Process algebra; finite automata; regular expressions; operational semantics

##  1 Introduction

It is an honor to write this paper in celebration of Jos Baeten on the
occasion of the publication of his _Festschrift_. I recall first becoming
aware of Jos late in my PhD studies at Cornell University. Early in my
doctoral career I had become independently interested in process algebra,
primarily through Robin Milner’s original monograph, _A Calculus of
Communicating Systems_ [Mil80], and indeed wound up writing my dissertation on
the topic. I was working largely on my own; apart from very stimulating
interactions with Prakash Panangaden, who was at Cornell at the time, there
were no researchers in the area at Cornell. It was in this milieu that I
stumbled across the seminal papers by Jos’ colleagues, Jan Bergstra and Jan
Willem Klop, describing the Algebra of Communicating Processes [BK84, BK85]. I
was impressed with their classically algebraic approach, and their semantic
accounts based on graph constructions. This, together with Milner’s focus on
operational semantics and the Communicating Sequential Processes community’s
on denotational semantics [BHR84], finally enabled me to truly understand the
deep and satisfying links between operational, denotational and axiomatic
approaches to not only process algebra, but to program semantics in general.

While Jos was not a co-author of the two papers just cited, he was an early
contributor to the process-algebraic field and has remained a prolific
researcher in both theoretical and applied aspects of the discipline. I have
followed his career, and admired his interest in both foundational theory and
practical applications of process theory, since completing my PhD in 1987. It
is this broader view on the impact of process algebra that is the motivation
for this note. Indeed, I will not focus so much on new theoretical results,
satisfying though they can be. Rather, I want recount a story about my usage
of process-algebra-inspired techniques to redevelop part of an undergraduate
course on automata theory that I taught for a number of years. Specifically, I
will discuss how I have used the Structural Operational Semantics (SOS)
techniques used extensively in process algebra to present what I have found to
be more satisfying ways than those typically covered in textbooks to construct
finite automata from regular expressions. Such constructions constitute a
proof of one half of Kleene’s Theorem [Kle56], which asserts a correspondence
between regular languages and those accepted by finite automata.

In the rest of this paper I present the construction and contrast it to the
constructions found in classical automata-theory textbooks such as [HMU06],
explaining why I find the work presented here preferable from a pedagogical
point of view. I also briefly situate the work in the setting of an efficient
technique [BS86] used in practice for converting regular expressions to finite
automata. The messsage I hope to convey is that in addition to contributing
foundational understanding to notions of concurrent computation, process
algebra can also cast new light on well-understood automaton constructions as
well, and that pioneers in process algebra, such as Jos Baeten, are doubly
deserving of the accolades they receive from the research community.

##  2 Alphabets, Languages, Regular Expressions and Automata

This section reviews the definitions and notation used later in this note for
formal languages, regular expressions and finite automata. In the interest of
succinctness the definitions depart slightly from those found in automata-
theory textbooks, although notationally I try to follow the conventions used
in those books.

###  2.1 Alphabets and Languages

At their most foundational level digital computers are devices for computing
with symbols. Alphabets and languages formalize this intuition mathematically.

[Alphabet, word]

  1. 1.

An _alphabet_ is a finite non-empty set $\Sigma$ of symbols.

  2. 2.

A _word_ over alphabet $\Sigma$ is a finite sequence $a_{1}\ldots a_{k}$ of
elements from $\Sigma$. We say that $k$ is the _length_ of $w$ in this case.
If $k=0$ we say $w$ is _empty_ ; we write $\varepsilon$ for the (unique) empty
word over $\Sigma$. Note that every $a\in\Sigma$ is also a (length-one) word
over $\Sigma$. We write $\Sigma^{*}$ for the set of all words over $\Sigma$.

  3. 3.

If $w_{1}=a_{1}\ldots a_{k}$ and $w_{2}=b_{1}\ldots b_{\ell}$ are words over
$\Sigma$ then the _concatenation_ , $w_{1}\cdot w_{2}$, of $w_{1}$ and $w_{2}$
is the word $a_{1}\ldots a_{k}b_{1}\ldots b_{n}$. Note that
$w\cdot\varepsilon=\varepsilon\cdot w=w$ for any word $w$. We often omit
$\cdot$ and write $w_{1}w_{2}$ for the concatenation of $w_{1}$ and $w_{2}$.

  4. 4.

A _language_ $L$ over alphabet $\Sigma$ is a subset of $\Sigma^{*}$. The set
of all languages over $\Sigma$ is the set of all subsets of $\Sigma^{*}$, and
is written $2^{\Sigma^{*}}$ following standard mathematical conventions.

Since languages over $\Sigma^{*}$ are sets, general set-theoretic operations,
including $\cup$ (union), $\cap$ (intersection) and $-$ (set difference) may
be applied to them. Other, language-specific operations may also be defined.

[Language concatenation, Kleene closure] Let $\Sigma$ be an alphabet.

  1. 1.

Let $L_{1},L_{2}\subseteq\Sigma^{*}$ be languages over $\Sigma$. Then the
_concentation_ , $L_{1}\cdot L_{2}$, of $L_{1}$ and $L_{2}$ is defined as
follows.

$L_{1}\cdot L_{2}=\\{w_{1}\cdot w_{2}\mid w_{1}\in L_{1}\textnormal{ and
}w_{2}\in L_{2}\\}$

  2. 2.

Let $L\subseteq\Sigma^{*}$ be a language over $\Sigma$. Then the _Kleene
closure_ , $L^{*}$, of $L$ is defined inductively as follows.111Textbooks
typically define $L^{*}$ differently, by first introducing $L^{i}$ for $i\geq
0$ and then taking $L^{*}=\bigcup_{i=0}^{\infty}L^{i}$

     * •

$\varepsilon\in L^{*}$

     * •

If $w_{1}\in L$ and $w_{2}\in L^{*}$ then $w_{1}\cdot w_{2}\in L^{*}$.

###  2.2 Regular Expressions

_Regular expressions_ provide a notation for defining languages.

[Regular expression] Let $\Sigma$ be an alphabet. Then the set,
$\mathcal{R}(\Sigma)$, of _regular expressions_ over $\Sigma$ is defined
inductively as follows.

  * •

$\emptyset\in\mathcal{R}(\Sigma)$.

  * •

$\varepsilon\in\mathcal{R}(\Sigma)$.

  * •

If $a\in\Sigma$ then $a\in\mathcal{R}(\Sigma)$.

  * •

If $r_{1}\in\mathcal{R}(\Sigma)$ and $r_{2}\in\mathcal{R}(\Sigma)$ then
$r_{1}+r_{2}\in\mathcal{R}(\Sigma)$ and $r_{1}\cdot
r_{2}\in\mathcal{R}(\Sigma)$.

  * •

If $r\in\mathcal{R}(\Sigma)$ then $r^{*}\in\mathcal{R}(\Sigma)$.

It should be noted that $\mathcal{R}(\Sigma)$ is a set of expressions; the
occurrences of $\emptyset,\varepsilon,+,\cdot$ and ∗ are symbols that do not
innately possess any meaning, but must instead be given a semantics. This is
done by interpreting regular expressions mathematically as languages. The
formal definition takes the form of a function,
$\mathcal{L}\in\mathcal{R}(\Sigma)\rightarrow 2^{\Sigma^{*}}$ assigning a
language $\mathcal{L}(r)\subseteq\Sigma^{*}$ to regular expression $r$.

[Language of a regular expression, regular language] Let $\Sigma$ be an
alphabet, and $r\in\mathcal{R}(\Sigma)$ a regular expression over $\Sigma$.
Then the _language_ , $\mathcal{L}(r)\subseteq\Sigma^{*}$, associated with $r$
is defined inductively as follows.

$\mathcal{L}(r)=\left\\{\begin{array}[]{lp{5cm}}\emptyset&if $r=\emptyset$\\\
\\{\varepsilon\\}&if $r=\varepsilon$\\\ \\{a\\}&if $r=a$ and $a\in\Sigma$\\\
\mathcal{L}(r_{1})\cup\mathcal{L}(r_{2})&if $r=r_{1}+r_{2}$\\\
\mathcal{L}(r_{1})\cdot\mathcal{L}(r_{2})&if $r=r_{1}\cdot r_{2}$\\\
(\mathcal{L}(r^{\prime}))^{*}&if $r=(r^{\prime})^{*}$\end{array}\right.$

A language $L\subseteq\Sigma^{*}$ is _regular_ if and only if there is a
regular expression $r\in\mathcal{R}(\Sigma)$ such that $\mathcal{L}(r)=L$.

###  2.3 Finite Automata

Traditional accounts of finite automata typically introduce three variations
of the notion: deterministic (DFA), nondeterministic (NFA), and
nondeterministic with $\varepsilon$-transitions (NFA-$\varepsilon$). I will do
the same, although I will do so in a somewhat different order than is typical.

[Nondeterministic Finite Automaton (NFA)] A _nondeterministic finite automata_
(NFA) is a tuple $(Q,\Sigma,\delta,q_{I},F)$, where:

  * •

$Q$ is a finite non-empty set of _states_ ;

  * •

$\Sigma$ is an _alphabet_ ;

  * •

$\delta\subseteq Q\times\Sigma\times Q$ is the _transition relation_ ;

  * •

$q_{I}\in Q$ is the _initial state_ ; and

  * •

$F\subseteq Q$ is the set of _accepting_ , or _final_ , states.

This definition of NFA differs slightly from e.g. [HMU06] in that $\delta$ is
given as relation rather than function in $Q\times\Sigma\rightarrow 2^{Q}$. It
also defines the form of a NFA but not the sense in which it is indeed a
machine for processing words in a language. The next definition does this by
associating a language $\mathcal{L}(M)$ with a given NFA
$M=(Q,\Sigma,\delta,q_{I},F)$.

[Language of a NFA] Let $M=(Q,\Sigma,\delta,q_{I},F)$ be a NFA.

  1. 1.

Let $q\in Q$ be a state of $M$ and $w\in\Sigma^{*}$ be a word over $\Sigma$.
Then $M$ _accepts_ $w$ from $q$ if and only if one of the following holds.

     * •

$w=\varepsilon$ and $q\in F$; or

     * •

$w=aw^{\prime}$ some $a\in\Sigma$ and $w^{\prime}\in\Sigma^{*}$, and there
exists $(q,a,q^{\prime})\in\delta$ such that $M$ accepts $w^{\prime}$ from
$q^{\prime}$.

  2. 2.

The _language_ , $\mathcal{L}(M)$, accepted by $M$ is defined as follows.

$\mathcal{L}(M)=\\{w\in\Sigma^{*}\mid M\textnormal{ accepts }w\textnormal{
from }q_{I}\\}$

Deterministic Finite Automata (DFAs) constitute a subclass of NFAs whose
transition relation is deterministic, in a precisely defined sense.

[Deterministic Finite Automaton (DFA)] NFA $M=(Q,\Sigma,\delta,q_{I},F)$ is a
_deterministic finite automaton_ (DFA) if and only if $\delta$ satisfies the
following: for every $q\in Q$ and $a\in\Sigma$, there exists exactly one
$q^{\prime}$ such that $(q,a,q^{\prime})\in\delta$.

Since DFAs are NFAs the definition of $\mathcal{L}$ in Definition 2.3 is
directly applicable to them as well. NFAs with $\epsilon$-transitions are now
defined as follows.

[NFAs with $\varepsilon$-Transitions] A _nondeterministic automaton with
$\varepsilon$-transitions_ (NFA-$\varepsilon$) is a tuple
$(Q,\Sigma,\delta,q_{I},F)$, where:

  * •

$Q$ is a nonempty finite set of _states_ ;

  * •

$\Sigma$ is an _alphabet_ , with $\varepsilon\not\in\Sigma$;

  * •

$\delta\subseteq Q\times(\Sigma\cup\\{\varepsilon\\})\times Q$ is the
_transition relation_ ;

  * •

$q_{I}\in Q$ is the _initial state_ ; and

  * •

$F$ is the set of _accepting_ , or _final_ , states.

An NFA-$\varepsilon$ is like a NFA except that some transitions can be labeled
with the empty string $\varepsilon$ rather than a symbol from $\Sigma$. The
intution is that a transition of form $(q,\varepsilon,q^{\prime})$ can occur
without consuming any symbol as an input. Formalizing this intuition, and
defining $\mathcal{L}(M)$ for NFA-$\varepsilon$, may be done as follows.

[Language of a NFA-$\varepsilon$] Let $M=(Q,\Sigma,\delta,q_{I},F)$ be a
NFA-$\varepsilon$.

  1. 1.

Let $q\in Q$ and $w\in\Sigma^{*}$. Then $M$ _accepts_ $w$ _from_ $q$ if and
only if one of the following holds.

     * •

$w=\varepsilon$ and $q^{\prime}\in F$; or

     * •

$w=aw^{\prime}$ for some $a\in\Sigma$ and $w^{\prime}\in\Sigma^{*}$ and there
exists $q^{\prime}\in Q$ such that $(q,a,q^{\prime})\in\delta$ and $M$ accepts
$w^{\prime}$ from $q^{\prime}$; or

     * •

there exists $q^{\prime}\in Q$ such that $(q,\varepsilon,q^{\prime})\in\delta$
and $M$ accepts $w$ from $q^{\prime}$.

  2. 2.

The _language_ , $\mathcal{L}(M)$, accepted by $M$ is defined as follows.

$\mathcal{L}(M)=\\{w\in\Sigma^{*}\mid M\textnormal{ accepts }w\textnormal{
from }q_{I}\\}$

Defining the language of a NFA-$\varepsilon$ requires redefining the notion of
a machine accepting a string from state $q$ as given in the definition of the
language of a NFA. This redefinition reflects the essential difference between
$\varepsilon$-transitions and those labeled by alphabet symbols.

The three types of automata have differences in form, but equivalent
expressive power. It should first be noted that, just as every DFA is already
a NFA, every NFA is also a NFA-$\varepsilon$, namely, a NFA-$\varepsilon$ with
no $\varepsilon$-transitions. Thus, every language accepted by some DFA is
also accepted by some NFA, and every language accepted by some NFA is accepted
by some NFA-$\varepsilon$. The next theorem establishes the converses of these
implications.

######  Theorem 1 (Equivalence of DFAs, NFAs and NFA-$\varepsilon$s).

  1. 1.

Let $M$ be a NFA. Then there is a DFA $D(M)$ such that
$\mathcal{L}(D(M))=\mathcal{L}(M)$.

  2. 2.

Let $M$ be a NFA-$\varepsilon$. Then there is a NFA $N(M)$ such that
$\mathcal{L}(N(M))=\mathcal{L}(M)$.

######  Proof 2.1.

The proof of Case (1) involves the well-known subset construction, whereby
each subset of states in $M$ is associated with a single state in $D(M)$. The
proof of Case (2) typically relies on defining the $\varepsilon$ closure of a
set of states, namely, the set of states reachable from the given set via a
sequence of zero or more $\varepsilon$-transitions. This notion is used to
define the transition relation of $N(M)$ as well as its set of accepting
states.

##  3 Kleene’s Theorem

Given the definitions in the previous section it is now possible to state
Kleene’s Theorem succinctly.

######  Theorem 2 (Kleene’s Theorem).

Let $\Sigma$ be an alphabet. Then $L\subseteq\Sigma^{*}$ is regular if and
only if there is a DFA $M$ such that $\mathcal{L}(M)=L$.

The proof of this theorem is usually split into two pieces. The first involves
showing that for any regular expression $r$, there is a finite automaton $M$
(DFA, NFA or NFA-$\varepsilon$) such that $\mathcal{L}(M)=\mathcal{L}(r)$.
Theorem 1 then ensures that the resulting finite automaton, if it is not
already a DFA, can be converted into one in a language-preserving manner. The
second shows how to convert a DFA $M$ into a regular expression $r$ in such a
way that $\mathcal{L}(r)=\mathcal{L}(M)$; there are several algorithms for
this in the literature, including the classic dynamic-programming-based method
of Kleene [Kle56] and equation-solving methods that rely on Arden’s Lemma
[Ard61].

From a practical standpoint, the conversion of regular expressions to finite
automata is the more important, since regular expressions are textual and are
used consequently as the basis for string search and processing. For this
reason, I believe that teaching this construction is especially keyin
automata-theory classes, and this where my complaint with the approaches in
traditional automata-theory texts originates.

To understand the basis for my dissatisfaction, let us review the construction
presented in [HMU06], which explains how to convert regular expression $r$
into NFA-$\varepsilon$ $M_{r}$ in such a way that
$\mathcal{L}(r)=\mathcal{L}(M_{r})$. The method is based on the construction
due to Ken Thompson [Tho68] and produces NFA-$\varepsilon$ $M_{r}$ with the
following properties.

  * •

The initial state $q_{I}$ has no incoming transitions: that is, there exists
no $(q,\alpha,q_{I})\in\delta$.

  * •

There is a single accepting state $q_{F}$, and $q_{F}$ has no outgoing
transitions: that is, $F=\\{q_{F}\\}$, and there exists no
$(q_{F},\alpha,q^{\prime})\in\delta$.

The approach proceeds inductively on the structure of $r$. For example, if
$r=(r^{\prime})^{*}$, then assume that
$M_{r^{\prime}}=(Q,\Sigma,\delta,q_{I},\\{q_{F}\\})$ meeting the above
constraints has been constructed. Then $M_{r}$ is built as follows. First, let
$q_{I}^{\prime}\not\in Q$ and $q_{F}^{\prime}\not\in Q$ be new states. Then
$M_{r}=(Q\cup\\{q_{I}^{\prime},q_{F}^{\prime}\\},\Sigma,\delta^{\prime},\\{q_{F}^{\prime}\\})$,
where

$\delta^{\prime}=\delta\cup\\{(q_{I}^{\prime},\varepsilon,q_{I}),(q_{I}^{\prime},\varepsilon,q_{F}^{\prime}),(q_{F},\varepsilon,q_{I}),(q_{F},\varepsilon,q_{F}^{\prime})\\}.$

It can be shown that $M_{r}$ satisfies the requisite properties and that
$\mathcal{L}(M_{r})=(\mathcal{L}(r^{\prime}))^{*}$.

Mathematically, the construction of $M_{r}$ is wholly satisfactory: it has the
required properties and can be defined relatively easily, albeit at the cost
of introducing new states and transitions. The proof of correctness is perhaps
somewhat complicated, owing to the definition of $\mathcal{L}(M)$ and the
subtlety of $\varepsilon$-transitions, but it does acquaint students with
definitions via structural induction on regular expressions.

My concern with the construction, however, is several-fold. On the one hand,
it does require the introduction of the notion of NFA-$\varepsilon$, which is
indeed more complex that that of NFA. In particular, the definition of
acceptance requires allowing transitions that consume no symbol in the input
word. On the other hand, the accretion of the introduction of new states at
each state in the construction makes it difficult to test students on their
understanding of the construction in an exam setting. Specifically, even for
relatively small regular expressions the literal application of the
construction yields automata with too many states and transitions to be doable
during the typical one-hour midterm exam for which US students would be tested
on the material. Finally, the construction bears no resemblance to algorithms
used in practice for construction finite automata from regular expressions. In
particular routines such as the Berry-Sethi procedure [BS86] construct DFAs
directly from regular expressions, completely avoiding the need for
NFA-$\varepsilon$s, or indeed NFAs, altogether.

The Berry-Sethi procedure is subtle and elegant, and relies on concepts, such
as Brzozowski derivatives [Brz64], that I would view as too specialized for an
undergraduate course on automata theory. Consequently, I would not be in favor
of covering them in an undergraduate classroom setting. Instead, in the next
section I give a technique, based on operational semantics in process algebra,
for construction NFAs from regular expressions. The resulting NFAs are small
enough for students to construct during exams, and the construction has other
properties, including the capacity for introducing other operations that
preserve regularity, that are pedagogically useful.

##  4 NFAs via Structural Operational Semantics

This section describes an approach based on _Structural Operational Semantics_
(SOS) [Plo81, Plo04] for constructing NFAs from regular expressions.
Specifically, I will define a (small-step) operational semantics for regular
expressions on the basis of the structure of regular expressions, and use the
semantics to construct the requisite NFAs. The construction requires no
$\varepsilon$-transitions and yields automata with at most one more state
state than the size of the regular expression from which they are derived.

Following the conventions in the other parts of this paper I give the SOS
rules using notation typically found in automata-theory texts. In particular,
the SOS specification is given in natural language, as a collection of if-then
statements, and not via inference rules. I use this approach in the classroom
to avoid having to introduce notations for inference rules. In the appendix I
give the more traditional SOS presentation.

###  4.1 An Operational Semantics for Regular Expressions

In what follows fix alphabet $\Sigma$. The basis for the operational semantics
of regular expressions consists of a relation,
$\xrightarrow{}\subseteq\mathcal{R}(\Sigma)\times\Sigma\times\mathcal{R}(\Sigma)$,
and a predicate $\surd\subseteq\mathcal{R}(\Sigma)$. In what follows I will
write $r\xrightarrow{a}r^{\prime}$ and $r\surd$ in lieu of
$(r,a,r^{\prime})\in\,\xrightarrow{}$ and $r\in\surd$. The intuitions are as
follows.

  1. 1.

$r\surd$ is intended to hold if and only if $\varepsilon\in\mathcal{L}(r)$.
This is used in defining accepting states.

  2. 2.

$r\xrightarrow{a}r^{\prime}$ is intended to reflect the following about
$\mathcal{L}(r)$: one way to build a word in $\mathcal{L}(r)$ is to start with
$a\in\Sigma$ and then finish it with a word from $\mathcal{L}(r^{\prime})$.

Using these relations, I then show how to build a NFA from $r$ whose states
are regular expressions, whose transitions are given by $\xrightarrow{}$, and
whose final states are defined using $\surd$.

#### Defining $\surd$ and $\xrightarrow{}$

We now define $\surd$. [Definition of $\surd$] Predicate $r\surd$ is defined
inductively on the structure of $r\in\mathcal{R}(\Sigma)$ as follows.

  * •

If $r=\varepsilon$ then $r\surd$.

  * •

If $r=(r^{\prime})^{*}$ for some $r^{\prime}\in\mathcal{R}(\Sigma)$ then
$r\surd$.

  * •

If $r=r_{1}+r_{2}$ for some $r_{1},r_{2}\in\mathcal{R}(\Sigma)$, and
$r_{1}\surd$, then $r\surd$.

  * •

If $r=r_{1}+r_{2}$ for some $r_{1},r_{2}\in\mathcal{R}(\Sigma)$, and
$r_{2}\surd$, then $r\surd$.

  * •

If $r=r_{1}\cdot r_{2}$ for some $r_{1},r_{2}\in\mathcal{R}(\Sigma)$, and
$r_{1}\surd$ and $r_{2}\surd$, then $r\surd$.

From the definition, one can see it is not the case that $\emptyset\surd$ or
$a\surd$, for any $a\in\Sigma$, while both $\varepsilon\surd$ and $r^{*}\surd$
always. This accords with the definition of $\mathcal{L}(r)$;
$\varepsilon\not\in\mathcal{L}(\emptyset)=\emptyset$, and
$\varepsilon\not\in\mathcal{L}(a)=\\{a\\}$, while
$\varepsilon\in\mathcal{L}(\varepsilon)=\\{\varepsilon\\}$ and $\varepsilon\in
L^{*}$ for any language $L\subseteq\Sigma^{*}$, and in particular for
$L=\mathcal{L}(r)$ for regular expression $r$. The other cases in the
definition reflect the fact that $\varepsilon\in\mathcal{L}(r_{1}+r_{2})$ can
only hold if $\varepsilon\in\mathcal{L}(r_{1})$ or
$\varepsilon\in\mathcal{L}(r_{2})$, since $+$ is interpreted as set union, and
that $\varepsilon\in\mathcal{L}(r_{1}\cdot r_{2})$ can only be true if
$\varepsilon\in\mathcal{L}(r_{1})$ and $\varepsilon\in\mathcal{L}(r_{2})$,
since regular-expression operator $\cdot$ is interpreted as language
concatenation. We have the following examples.

$\begin{array}[]{lp{3in}}(\varepsilon\cdot a^{*})\surd&since
$\varepsilon\surd$ and $a^{*}\surd$.\\\ \neg(a+b)\surd&since neither $a\surd$
nor $b\surd$.\\\ (01+(1+01)^{*})\surd&since $(1+01)^{*}\surd$.\\\
\neg(01(1+01)^{*})\surd&since $\neg(01)\surd$.\\\ \end{array}$

We also use structural induction to define $\xrightarrow{}$. [Definition of
$\xrightarrow{}$] Relation $r\xrightarrow{a}r^{\prime}$, where
$r,r^{\prime}\in\mathcal{R}(\Sigma)$ and $a\in\Sigma$, is defined inductively
on $r$.

  * •

If $r=a$ and $a\in\Sigma$ then $r\xrightarrow{a}\varepsilon$.

  * •

If $r=r_{1}+r_{2}$ and $r_{1}\xrightarrow{a}r_{1}^{\prime}$ then
$r\xrightarrow{a}r_{1}^{\prime}$.

  * •

If $r=r_{1}+r_{2}$ and $r_{2}\xrightarrow{a}r_{2}^{\prime}$ then
$r\xrightarrow{a}r_{2}^{\prime}$.

  * •

If $r=r_{1}\cdot r_{2}$ and $r_{1}\xrightarrow{a}r_{1}^{\prime}$ then
$r\xrightarrow{a}r_{1}^{\prime}\cdot r_{2}$.

  * •

If $r=r_{1}\cdot r_{2}$, $r_{1}\surd$ and $r_{2}\xrightarrow{a}r_{2}^{\prime}$
then $r\xrightarrow{a}r_{2}^{\prime}$.

  * •

If $r=(r^{\prime})^{*}$ and $r^{\prime}\xrightarrow{a}r^{\prime\prime}$ then
$r\xrightarrow{a}r^{\prime\prime}\cdot(r^{\prime})^{*}$.

The definition of this relation is somewhat complex, but the idea that it is
trying to capture is relatively simple: $r\xrightarrow{a}r^{\prime}$ if one
can build words in $\mathcal{L}(r)$ by taking the $a$ labeling
$\xrightarrow{}$ and appending a word from $\mathcal{L}(r^{\prime})$. So we
have the rule $a\xrightarrow{a}\varepsilon$ for $a\in\Sigma$, while the rules
for $+$ follow from the fact that
$\mathcal{L}(r_{1}+r_{2})=\mathcal{L}(r_{1})\cup\mathcal{L}(r_{2})$. The cases
for $r_{1}\cdot r_{2}$ in essence state that $aw\in\mathcal{L}(r_{1}\cdot
r_{2})$ can hold either if there is a way of splitting $w$ into $w_{1}$ and
$w_{2}$ such that $aw_{1}$ is in the language of $r_{1}$ and $w_{2}$ is in the
language of $r_{2}$, or if $\varepsilon$ is in the language of $r_{1}$ and
$aw$ is in the language of $r_{2}$. Finally, the rule for $(r^{\prime})^{*}$
essentially permits “looping”. As examples, we have the following.

$\begin{array}[]{lp{8cm}}a+b\xrightarrow{a}\varepsilon&by the rules for $a$
and $+$.\\\ (abb+a)^{*}\xrightarrow{a}\varepsilon bb(abb+a)^{*}&by the rules
for $a$, $\cdot$, $+$, and ${}^{*}$.\end{array}$

In this latter example, note that applying the definition literally requires
the inclusion of the $\varepsilon$ in $\varepsilon bb(abb+a)^{*}$. This is
because the case for $a$ says that $a\xrightarrow{a}\varepsilon$, meaning that
$abb\xrightarrow{a}\varepsilon bb$, etc. However, when there are leading
instances of $\varepsilon$ like this, I will sometimes leave them out, and
write $abb\xrightarrow{a}bb$ rather than $abb\xrightarrow{a}\varepsilon
bb$.222This convention can be formalized by introducing a special case in the
definition of $\xrightarrow{}$ for $a\cdot r_{2}$ and distinguishing the
current two cases for $r_{1}\cdot r_{2}$ to apply only when
$r_{1}\not\in\Sigma.$

The following lemmas about $\surd$ and $\xrightarrow{}$ formally establish the
intuitive properties that they should have.

######  Lemma 3.

Let $r\in\mathcal{R}(\Sigma)$ be a regular expression. Then $r\surd$ if and
only if $\varepsilon\in\mathcal{L}(r)$.

######  Proof 4.1.

The proof proceeds by structural induction on $r$. Most cases are left to the
reader; we only consider the $r=r_{1}\cdot r_{2}$ case here. The induction
hypothesis states that $r_{1}\surd$ if and only if
$\varepsilon\in\mathcal{L}(r_{1})$ and $r_{2}\surd$ if and only if
$\varepsilon\in\mathcal{L}(r_{2})$. One reasons as follows.

$\begin{array}[]{r@{\textnormal{ iff }}lp{6cm}}r\surd&r_{1}\surd\textnormal{
and }r_{2}\surd&Definition of $\surd$\\\
&\varepsilon\in\mathcal{L}(r_{1})\textnormal{ and
}\varepsilon\in\mathcal{L}(r_{2})&Induction hypothesis\\\
&\varepsilon\in(\mathcal{L}(r_{1}))\cdot(\mathcal{L}(r_{2}))&Property of
concatenation\\\ &\varepsilon\in\mathcal{L}(r_{1}\cdot r_{2})&Definition of
$\mathcal{L}(r_{1}\cdot r_{2})$\\\ &\varepsilon\in\mathcal{L}(r)&$r=r_{1}\cdot
r_{2}$\end{array}$

######  Lemma 4.

Let $r\in\mathcal{R}(\Sigma)$, $a\in\Sigma$, and $w\in\Sigma^{*}$. Then
$aw\in\mathcal{L}(r)$ if and only if there is an
$r^{\prime}\in\mathcal{R}(\Sigma)$ such that $r\xrightarrow{a}r^{\prime}$ and
$w\in\mathcal{L}(r^{\prime})$.

######  Proof 4.2.

The proof proceeds by structural induction on $r$. We only consider the case
$r=(r^{\prime})^{*}$ in detail; the others are left to the reader. The
induction hypothesis asserts that for all $a$ and $w^{\prime}$,
$aw^{\prime}\in\mathcal{L}(r^{\prime})$ if and only if there is an
$r^{\prime\prime}$ such that $r^{\prime}\xrightarrow{a}r^{\prime\prime}$ and
$w^{\prime}\in\mathcal{L}(r^{\prime\prime})$. We reason as follows.

$\begin{array}[]{r@{\textnormal{ iff
}}lp{4.8cm}}aw\in\mathcal{L}(r)&aw\in\mathcal{L}((r^{\prime})^{*})&$r=(r^{\prime})^{*}$\\\
&aw\in(\mathcal{L}(r^{\prime}))^{*}&Definition of
$\mathcal{L}((r^{\prime})^{*})$\\\ &aw=w_{1}\cdot w_{2}\textnormal{ some
}w_{1}\in\mathcal{L}(r^{\prime}),w_{2}\in(\mathcal{L}(r^{\prime}))^{*}&Definition
of Kleene closure\\\ &w_{1}=a\cdot w_{1}^{\prime}\textnormal{ some
}w_{1}^{\prime}&Property of Kleene closure\\\
&r^{\prime}\xrightarrow{a}r^{\prime\prime}\textnormal{ some
}r^{\prime\prime}\textnormal{ with
}w_{1}^{\prime}\in\mathcal{L}(r^{\prime\prime})&Induction hypothesis\\\
&r\xrightarrow{a}r^{\prime\prime}\cdot(r^{\prime})^{*}&Definition of
$\xrightarrow{}$\\\ &w_{1}^{\prime}\cdot
w_{2}\in\mathcal{L}(r^{\prime\prime})\cdot\mathcal{L}((r^{\prime})^{*})&Definition
of concatenation\\\ &w_{1}^{\prime}\cdot
w_{2}\in\mathcal{L}(r^{\prime\prime}\cdot(r^{\prime})^{*})&Definition of
$\mathcal{L}(r^{\prime\prime}\cdot(r^{\prime})^{*})$\\\
&r\xrightarrow{a}r^{\prime\prime}\cdot(r^{\prime})^{*}\textnormal{ and
}w\in\mathcal{L}(r^{\prime\prime}\cdot(r^{\prime})^{*})&$w=w_{1}^{\prime}\cdot
w_{2}$\end{array}$

Appendix A contains definitions of $\surd$ and $\xrightarrow{}$ in the more
usual inference-rule style used in SOS specifications.

###  4.2 Building Automata using $\surd$ and $\xrightarrow{}$

That $\surd$ and $\xrightarrow{}$ may be used to build NFAs derives from how
they may be used to determine whether a string is in the language of a regular
expression. Consider the following sequence of transitions starting from the
regular expression $(abb+a)^{*}$.

$(abb+a)^{*}\xrightarrow{a}bb(abb+a)^{*}\xrightarrow{b}b(abb+a)^{*}\xrightarrow{b}(abb+a)^{*}\xrightarrow{a}(abb+a)^{*}$

Using Lemma 4 four times, we can conclude that if
$w\in\mathcal{L}((abb+a)^{*})$, then $abba\cdot w\in\mathcal{L}((abb+a)^{*})$
also. In addition, since $(abb+a)^{*}\surd$, it follows from Lemma 3 that
$\varepsilon\in\mathcal{L}((abb+a)^{*})$. Since $abba\cdot\varepsilon=abba$,
it follows that $abba\in\mathcal{L}((abb+a)^{*})$.

More generally, if there is a sequence of transitions
$r_{0}\xrightarrow{a_{1}}r_{1}\cdots\xrightarrow{a_{n}}r_{n}$ and
$r_{n}\surd$, then it follows that $a_{1}\ldots a_{n}\in\mathcal{L}(r_{0})$,
and vice versa. This observation suggests the following strategy for building
a NFA from a regular expression $r$.

  1. 1.

Let the states be all possible regular expressions that can be reached by some
sequence of transitions from $r$.

  2. 2.

Take $r$ to be the start state.

  3. 3.

Let the transitions be given by $\xrightarrow{}$.

  4. 4.

Let the accepting states be those regular expressions $r^{\prime}$ reachable
from $r$ for which $r^{\prime}\surd$ holds.

Of course, this construction is only valid if the set of all possible regular
expressions mentioned in Step (1) is finite, since NFAs are required to have a
finite number of states. In fact, a stronger result can be proved. First,
recall the definition of the size, $|r|$, of regular expression $r$.

[Size of a regular expression] The size, $|r|$, of $r\in\mathcal{R}(\Sigma)$
is defined inductively as follows.

$|r|=\left\\{\begin{array}[]{lp{8cm}}1&if $r=\varepsilon,r=\emptyset,$ or
$r=a$ for some $a\in\Sigma$\\\ |r^{\prime}|+1&if $r=(r^{\prime})^{*}$\\\
|r_{1}|+|r_{2}|+1&if $r=r_{1}+r_{2}$ or $r=r_{1}\cdot
r_{2}$\end{array}\right.$

Intuitively, $|r|$ counts the number of regular-expression operators in $r$.
The _reachability set_ of regular expression $r$ can now be defined in the
usual manner.

Let $r\in\mathcal{R}(\Sigma)$ be a regular expression. Then the set
$RS(r)\subseteq\mathcal{R}(\Sigma)$ of regular expressions _reachable from_
$r$ is defined recursively as follows.

  * •

$r\in RS(r)$.

  * •

If $r_{1}\in RS(r)$ and $r_{1}\xrightarrow{a}r_{2}$ for some $a\in\Sigma$,
then $r_{2}\in RS(r)$.

As an example, note that $|(abb+a)^{*}|=8$ and that

$RS((abb+a)^{*})=\\{(abb+a)^{*},\varepsilon bb(abb+a)^{*},\varepsilon
b(abb+a)^{*},\varepsilon(abb+a)^{*}\\},$

(In this case I have not applied my heuristic of suppressing leading
$\varepsilon$ expressions.) The following can now be provd.

######  Theorem 5.

Let $r\in\mathcal{R}(\Sigma)$ be a regular expression. Then
$|RS(r)|\leq|r|+1$.

######  Proof 4.3.

The proof proceeds by structural induction on $r$. There are six cases to
consider.

$r=\emptyset$

In this case $RS(r)=\\{\emptyset\\}$, and $|RS(r)|=1=|r|<|r|+1$.

$r=\varepsilon$

In this case $RS(r)=\\{\varepsilon\\}$, and $|RS(r)|=1=|r|<|r|+1$.

$r=a$ for some $a\in\Sigma$

In this case $RS(r)=\\{a,\varepsilon\\}$, and $|RS(r)|=2=|r|+1$.

$r=r_{1}+r_{2}$

In this case, $RS(r)\subseteq RS(r_{1})\cup RS(r_{2})$, and the induction
hypothesis guarantees that $|RS(r_{1})|\leq|r_{1}|+1$ and
$RS(r_{2})\leq|r_{2}|+1$. It then follows that

$|RS(r)|\leq|RS(r_{1})|+|RS(r_{2})|\leq|r_{1}|+|r_{2}|+2=|r|+1.$

$r=r_{1}\cdot r_{2}$

In this case it can be shown that $RS(r)\subseteq\\{r_{1}^{\prime}\cdot
r_{2}\mid r_{1}^{\prime}\in RS(r_{1})\\}\cup RS(r_{2})$. Since
$|\\{r_{1}^{\prime}\cdot r_{2}\mid r_{1}^{\prime}\in
RS(r_{1})\\}|=|RS(r_{1})|$, similar reasoning as in the $+$ case applies.

$r=(r^{\prime})^{*}$

In this case we have that $RS(r)\subseteq\\{r\\}\cup\\{r^{\prime\prime};r\mid
r^{\prime\prime}\in RS(r^{\prime})\\}$. Thus

$|RS(r)|\leq|RS(r^{\prime})|+1\leq|r^{\prime}|+2=|r|+1.$

This result shows not only that the sketched NFA construction given above
yields a finite number of states for given $r$, it in fact establishes that
this set of state is no larger than $|r|+1$. This highlights one of the main
reasons I opted to introduce this construction in my classes: small regular
expressions yield NFAs that are almost as small, and can be constructed
manually in an exam setting.

We can now formally define the construction of NFA $M_{r}$ from regular
expression $r$ as follows. Let $r\in\mathcal{R}(\Sigma)$ be a regular
expression. Then $M_{r}=(Q,\Sigma,q_{I},\delta,A)$ is the NFA defined as
follows.

  * •

$Q=RS(r)$.

  * •

$q_{I}=r$.

  * •

$\delta=\\{(r_{1},a,r_{2})\mid r_{1}\xrightarrow{a}r_{2}\\}$.

  * •

$F=\\{r^{\prime}\in Q\mid r^{\prime}\surd\\}$.

The next theorem establishes that $r$ and $M_{r}$ define the same languages.

######  Theorem 6.

Let $r\in\mathcal{R}(\Sigma)$ be a regular expression. The
$\mathcal{L}(r)=\mathcal{L}(M_{r})$.

######  Proof 4.4.

Relies on the fact that Lemmas 3 and 4 guarantee that $w=a_{1}\ldots
a_{n}\in\mathcal{L}(r)$ if and only if there is a regular expression
$r^{\prime}$ such that
$r\xrightarrow{a_{1}}\cdots\xrightarrow{a_{n}}r^{\prime}$ and
$r^{\prime}\surd$.

###  4.3 Computing $M_{r}$

This section gives a routine for computing $M_{r}$. It intertwines the
computation of the reachability set from regular expression $r$ with the
updating of the transition relation and set of accepting states. It relies on
the computation of the so-called _outgoing transitions_ of $r$; these are
defined as follows.

Let $r\in\mathcal{R}(\Sigma)$ be a regular expression. Then the set of
_outgoing transitions_ from $r$ is defined as the set $\\{(a,r^{\prime})\mid
r\xrightarrow{a}r^{\prime}\\}$. The outgoing transitions from $r$ consists of
pairs $(a,r^{\prime})$ that, when combined with $r$, constitute a valid
transition $r\xrightarrow{a}r^{\prime}$. Figure 1 defines a recursive
function, out, for computing the outgoing transitions of $r$. The routine uses
the structure of $r$ and the definition of $\xrightarrow{}$ to guide its
computation. For regular expressions of the form $\emptyset,\varepsilon$ and
$a\in\Sigma$, the definition of $\xrightarrow{}$ in Definition 4.1 immediately
gives all the transitions. For regular expressions built using $+,\cdot$ and
∗, one must first recursively compute the outgoing transitions of the
subexpressions of $r$ and then combine the results appropriately, based on the
cases given in the Definition 4.1.

$\textit{out}(r)=\left\\{\begin{array}[]{lp{10em}}\emptyset&if $r=\emptyset$
or $r=\varepsilon$\\\ \\{(a,\varepsilon)\\}&if $r=a\in\Sigma$\\\
\textit{out}(r_{1})\cup\textit{out}(r_{2})&if $r=r_{1}+r_{2}$\\\
\\{(a,r_{1}^{\prime}\cdot
r_{2})\mid(a,r_{1}^{\prime})\in\textit{out}(r_{1})\\}&\\\
\;\;\;\;\;\;\cup\;\\{(a,r_{2}^{\prime})\mid(a,r_{2}^{\prime})\in\textit{out}(r_{2})\land
r_{1}\surd\\}&if $r=r_{1}\cdot r_{2}$\\\
\\{(a,r^{\prime\prime}\cdot(r^{\prime})^{*})\mid(a,r_{1}^{\prime})\in\textit{out}(r_{1})\\}&if
$r=(r^{\prime})^{*}$\end{array}\right.$ Figure 1: Calculating the outgoing
transitions of regular expressions.

The next lemma states that $\textit{out}(r)$ correctly computes the outgoing
transitions of $r$.

######  Lemma 7.

Let $r\in\mathcal{R}(\Sigma)$ be a regular expression, and let
$\textit{out}(r)$ be as defined in Figure 1. Then
$\textit{out}(r)=\\{(a,r^{\prime})\mid r\xrightarrow{a}r^{\prime}\\}$.

######  Proof 4.5.

By structural induction on $r$. The details are left to the reader.

Algorithm 1 contains pseudo-code for computing $M_{r}$. It maintains four
sets.

  * •

$Q$, a set that will eventually contain the states of $M_{r}$.

  * •

$F$, a set that will eventually contain the accepting states of $M_{r}$.

  * •

$\delta$, a set that will eventually contain the transition relation of
$M_{r}$.

  * •

$W$, the _work set_ , a subset of $Q$ containing states that have not yet had
their outgoing transitions computed or acceptance status determined.

The procedure begins by adding $r$, its input parameter, to both $Q$ and $W$.
It then repeatedly removes a state from $W$, determines if it should be added
to $F$, computes its outgoing transitions and updates $\delta$ appropriately,
and finally adds the target states in the outgoing transition set to both $Q$
and $W$ if they are not yet in $Q$ (meaning they have not yet been encountered
in the construction of $M_{r}$). The algorithm terminates when $W$ is empty.

1

2Algorithm NFA$(r)$

Input : Regular rexpression $r\in\mathcal{R}(\Sigma)$

Output : NFA $M_{r}=(Q,\Sigma,q_{I},\delta,F)$

3

$Q:=\\{r\\}$

// State set

$q_{I}:=r$

// Start state

$W:=\\{r\\}$

// Working set

$\delta:=\emptyset$

// Transition relation

$F:=\emptyset$

// Accepting states

4

5while  _$W\neq\emptyset$_ do

6 choose $r^{\prime}\in W$

7 $W:=W-\\{r^{\prime}\\}$

8 if  _$r^{\prime}\surd$ _ then

9 $F:=F\cup\\{r^{\prime}\\}$ // $r^{\prime}$ is an accepting state

$T=\textit{out}(r^{\prime})$

// Outgoing transitions of $r^{\prime}$

$\delta:=\delta\cup\\{r^{\prime},a,r^{\prime\prime})\mid(a,r^{\prime\prime})\in
T\\}$

// Update transition relation

10

11 foreach  _$(a,r^{\prime\prime})\in T$_ do

12 if  _$r^{\prime\prime}\not\in Q$_ then

$Q:=Q\cup\\{r^{\prime\prime}\\}$

// $r^{\prime\prime}$ is a new expression

13 $W:=W\cup\\{r^{\prime\prime}\\}$

14

15 end foreach

16

17 end while

18

19return $M_{r}=(Q,\Sigma,\delta,q_{I},F)$

Algorithm 1 Algorithm for computing NFA $M_{r}$ from regular expression $r$

Figure 2 gives the NFA resulting from applying the procedure to $(abb+a)^{*}$.
Figure 3, by way of contrast, shows the result of applying the routine in
[HMU06] to produce a NFA-$\varepsilon$ from the same regular expression.

$\;\;(abb+a)^{*}\;\;$$\varepsilon bb(abb+a)^{*}$$\;\varepsilon
b(abb+a)^{*}\;$$\;\varepsilon(abb+a)^{*}\;$$a$$a$$b$$b$$a$ Figure 2: NFA$(r)$
for $r=(abb+a)^{*}$.
$\varepsilon$$\varepsilon$$a$$\varepsilon$$b$$\varepsilon$$b$$a$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$
Figure 3: NFA-$\varepsilon$ for $(abb+a)^{*}$.

##  5 Discussion

The title of this note is “Better Automata through Process Algebra,” and I
want to revisit it in order to explain in what respects I regard the method
presented in here as producing “better automata.” Earlier I identified the
following motivations that prompted me to incorporate this approach in my
classroom instruction.

  * •

I wanted to produce NFAs rather than NFA-$\varepsilon$s. In large part this
was due to my desire not cover the notion of NFA-$\varepsilon$. The only place
this material is used in typical automata-theory textbooks is as a vehicle for
converting regular expressions into finite automata. By giving a construction
that avoids the use of $\varepsilon$-transitions, I could avoid covering
NFA-$\varepsilon$s and devote the newly freed lecture time to other topics. Of
course, this is only possible if the NFA-based construction does not require
more time to describe than the introduction of NFA-$\varepsilon$ and the
NFA-$\varepsilon$ construction.

  * •

I wanted the construction to be one that students could apply during an exam
to generate finite automata from regular expressions. The classical
construction found in [HMU06] and other books fails this test, in my opinion;
while the inductive definitions are mathematically pleasing, they yield
automata with too many states for students to be expected to apply them in a
time-constrained setting.

  * •

Related to the preceding point, I wanted a technique that students could
imagine being implemented and used in the numerous applications to which
regular expressions are applied. In such a setting, fewer states is better
than more states, all things considered.

This note has attempted to argue these points by giving a construction in
Definition 4.2 for constructing NFAs directly from regular expressions.
Theorem 5 estabishes that the number of states in these NFAs is at most one
larger than the size of the regular expression from which the NFAs are
generated; this provides guidance in preparing exam questions, as the size of
the NFAs students can be asked to generate are tightly bounded by the size of
the regular expression given in the exam. Finally, Algorithm 1 gives a “close-
to-code” account of the construction that hints at its implementability.
Indeed, several years ago a couple of students that I presented this material
to independently implemented the algorithm.

Beyond the points mentioned above, I think this approach has two other points
in its favor. The first is that is provides a basis for defining other
operators over regular expressions and proving that the class of regular
languages is closed with result to these operations. The ingredients for
introducing such a new operator and proving closure of regular languages with
respect to it can be summarized as follows.

  1. 1.

Extend the definition of $\mathcal{L}(r)$ given in Definition 2.2 to give a
language-theoretic semantics for the operator.

  2. 2.

Extend the definitions of $\surd$ and $\xrightarrow{}$ in Definitions 4.1 and
4.1 to give a small-step operations semantics for the operator.

  3. 3.

Extend the proofs of Lemmas 3 and 4 to establish connections between the
language semantics and the operational semantics.

  4. 4.

Prove that expressions extended with the new operator yield finite sets of
reachable expressions.

All of these steps involve adding new cases to the existing definitions and
lemmas, and altering Theorem 5 in the case of the last point. Once these are
done, Algorithm 1, with the definition of out given in Figure 1 suitably
modified to cover the new operator, can be used as is as a basis for
constructing NFAs from these extended classes of regular languages.

I have used parts of this approach in the classroom to ask students to prove
that synchronous product and interleaving operators can be shown to preserve
language regularity. Other operators, such as ones from process algebra, are
also candidates for these kinds of questions.

The second feature of the approach in this paper that I believe recommends it
is that the NFA construction is “on-the-fly”; the construction of a automaton
from a regular expression does not require the _a priori_ construction of
automata from subexpressions, meaning that the actual production of the
automaton can be intertwined with other operations, such as the checking of
whether a word belongs to the regular expression’s language. One does not need
to wait the construction of the full automaton, in other words, before putting
it to use.

Criticisms that I have heard of this approach center around two issues. The
first is that the construction of NFA $M_{r}$ from regular expression $r$ does
not use structural induction on $r$, unlike the classical constructions in
e.g. [HMU06]. I do not have much patience with the complaint, as the concepts
that $M_{r}$ is built on, namely $\surd$ and $\xrightarrow{}$, are defined
inductively, and the results proven about them require substantial use of
induction. The other complaint is that the notion of
$r\xrightarrow{a}r^{\prime}$ is “hard to understand.” It is indeed the case
that equipping regular expressions with an operational semantics is far
removed from the language-theoretic semantics typically given to these
expressions. That said, I would argue that the small-step operational
semantics considered here in fact exposes the essence of the relationship
between regular expressions and finite automata: this semantics enables
regular expressions to be executed, and in a way that can be captured via
automata.

I close this section with a brief discussion of the Berry-Sethi algorithm
[BS86], which is used in practice and produces deterministic finite automata.
This feature enables their technique to accommodate complementation, an
operation with respect to which regular languages are closed but which fits
uneasily with NFAs. From a pedagogical perspective, however, the algorithm
suffers somewhat as number of states in a DFA can be exponentially larger than
that size of the regular expression from which it is derived. A similar
criticism can be made of other techniques that rely on Brzozowsky derivatives
[Brz64], which also produce DFAs. There are interesting connections between
our operational semantics and these derivatives, but we exploit nondeterminacy
to keep the sizes of the resulting finite automata small.

##  6 Conclusions and Directions for Future Work

In this note I have presented an alternative approach for converting regular
expressions into finite automata. The method relies on defining an operational
semantics for regular expressions, and as such draws inspiration from the work
on process algebra undertaken by pioneers in that field, including Jos Baeten.
In contrast with classical techniques, the construction here does not require
transitions labeled by the empty word $\varepsilon$, and it yields automata
whose state sets are proportional in size to the regular expressions they come
from. The procedure can also be implemented in an on-the-fly manner, meaning
that the production of the automaton can be intertwined with other analysis
procedures as well.

Other algorithms studied in process algebra also have pedagogical promise, in
my opinion. One method, the Kanellakis-Smolka algorithm for computing
bisimulation equivalence [KS90], is a case in point. Partition-refinement
algorithms for computing langauge equivalence of deterministic automata have
been in existence for decades, but the details underpinning them are subtle
and difficult to present in an undergraduate automata-theory class, where
instructional time is at a premium. While not as efficient asymptotically as
the best procedures, the simplicity of the K-S technique recommends it, in my
opinion, both for equivalence checking and state-machine minimization.
Simulation-checking algorithms [HHK95] can also be used as a basis for
checking language containment among finite automata; these are interesting
because they do not require determinization of both automata being compared,
in general.

## References

  * [Ard61] Dean N Arden.  Delayed-logic and finite-state machines.  In 2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1961), pages 133–151. IEEE, 1961.
  * [BHR84] Stephen D. Brookes, C. A. R. Hoare, and A. W. Roscoe.  A theory of communicating sequential processes.  Journal of the ACM, 31(3):560–599, 1984.
  * [BK84] J.A. Bergstra and J.W. Klop.  Process algebra for synchronous communication.  Information and Control, 60(1):109–137, 1984.
  * [BK85] Jan A. Bergstra and Jan Willem Klop.  Algebra of communicating processes with abstraction.  Theoretical Computer Science, 37:77–121, 1985.
  * [Brz64] Janusz A. Brzozowski.  Derivatives of regular expressions.  Journal of the ACM (JACM), 11(4):481–494, 1964.
  * [BS86] Gerard Berry and Ravi Sethi.  From regular expressions to deterministic automata.  Theoretical Computer Science, 48:117–126, 1986.
  * [HHK95] Monika Rauch Henzinger, Thomas A. Henzinger, and Peter W. Kopke.  Computing simulations on finite and infinite graphs.  In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 453–462. IEEE, 1995.
  * [HMU06] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.  Introduction to Automata Theory, Languages, and Computation (3rd Edition).  Addison-Wesley Longman Publishing Co., Inc., Boston, 2006.
  * [Kle56] S.C. Kleene.  Representation of events in nerve nets and finite automata.  In Automata Studies, pages 3–41. Princeton University Press, 1956\.
  * [KS90] Paris C. Kanellakis and Scott A. Smolka.  Ccs expressions, finite state processes, and three problems of equivalence.  Information and Computation, 86(1):43–68, 1990.
  * [Mil80] Robin Milner.  A Calculus of Communicating Systems, volume 92 of Lecture Notes in Computer Science.  Springer, 1980.
  * [Plo81] Gordon D Plotkin.  A structural approach to operational semantics.  Technical report, Aarhus University, Denmark, 1981.
  * [Plo04] Gordon D Plotkin.  The origins of structural operational semantics.  The Journal of Logic and Algebraic Programming, 60:3–15, 2004.
  * [Tho68] Ken Thompson.  Programming techniques: Regular expression search algorithm.  Communications of the ACM, 11(6):419–422, June 1968.

##  Appendix A SOS Rules for $\surd$ and $\xrightarrow{}$

Here are the inference rules used to define $\surd$. They are given in the
form

$\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}\textit{premises}\\\ \hline\cr\\\\[-9.47217pt]
\textit{conclusion}\end{array}\\\ \hline\cr\end{array}$

with $-$ denoting an empty list of premises.

$\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt] \begin{array}[]{c}-\\\
\hline\cr\\\\[-9.47217pt] \varepsilon\surd\end{array}\\\
\hline\cr\end{array}\;\;\;\;\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}-\\\ \hline\cr\\\\[-9.47217pt] r^{*}\surd\end{array}\\\
\hline\cr\end{array}\;\;\;\;\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}r_{1}\surd\\\ \hline\cr\\\\[-9.47217pt]
(r_{1}+r_{2})\surd\end{array}\\\
\hline\cr\end{array}\;\;\;\;\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}r_{2}\surd\\\ \hline\cr\\\\[-9.47217pt]
(r_{1}+r_{2})\surd\end{array}\\\
\hline\cr\end{array}\;\;\;\;\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}r_{1}\surd\;\;\;\;r_{2}\surd\\\ \hline\cr\\\\[-9.47217pt]
(r_{1}\cdot r_{2})\surd\end{array}\\\ \hline\cr\end{array}$

Next are the rules for $\xrightarrow{}$.

$\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt] \begin{array}[]{c}-\\\
\hline\cr\\\\[-9.47217pt] a\xrightarrow{a}\varepsilon\end{array}\\\
\hline\cr\end{array}\;\;\;\;\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}r_{1}\xrightarrow{a}r_{1}^{\prime}\\\
\hline\cr\\\\[-9.47217pt]
r_{1}+r_{2}\xrightarrow{a}r_{1}^{\prime}\end{array}\\\
\hline\cr\end{array}\;\;\;\;\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}r_{2}\xrightarrow{a}r_{2}^{\prime}\\\
\hline\cr\\\\[-9.47217pt]
r_{1}+r_{2}\xrightarrow{a}r_{2}^{\prime}\end{array}\\\ \hline\cr\end{array}$
$\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}r_{1}\xrightarrow{a}r_{1}^{\prime}\\\
\hline\cr\\\\[-9.47217pt] r_{1}\cdot r_{2}\xrightarrow{a}r_{1}^{\prime}\cdot
r_{2}\end{array}\\\
\hline\cr\end{array}\;\;\;\;\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}r_{1}\surd\;\;\;\;r_{2}\xrightarrow{a}r_{2}^{\prime}\\\
\hline\cr\\\\[-9.47217pt] r_{1}\cdot
r_{2}\xrightarrow{a}r_{2}^{\prime}\end{array}\\\
\hline\cr\end{array}\;\;\;\;\begin{array}[]{|c|}\hline\cr\\\\[-9.47217pt]
\begin{array}[]{c}r\xrightarrow{a}r^{\prime}\\\ \hline\cr\\\\[-9.47217pt]
r^{*}\xrightarrow{a}r^{\prime}\cdot(r^{*})\end{array}\\\ \hline\cr\end{array}$


# Motif Identification using CNN-based Pairwise Subsequence Alignment Score
Prediction
††thanks: Identify applicable funding agency here. If none, delete this.

Ethan Moyer  School of Biomedical Engineering, Science and Health Systems
Drexel University
Philadelphia, PA
https://orcid.org/0000-0002-8023-3810  Anup Das  College of Engineering
Drexel University
Philadelphia, PA
https://orcid.org/0000-0002-5673-2636

###### Abstract

A common problem in bioinformatics is related to identifying gene regulatory
regions marked by relatively high frequencies of motifs, or deoxyribonucleic
acid sequences that often code for transcription and enhancer proteins.
Predicting alignment scores between subsequence k-mers and a given motif
enables the identification of candidate regulatory regions in a gene, which
correspond to the transcription of these proteins. We propose a one-
dimensional (1-D) Convolution Neural Network trained on k-mer formatted
sequences interspaced with the given motif pattern to predict pairwise
alignment scores between the consensus motif and subsequence k-mers. Our model
consists of fifteen layers with three rounds of a one-dimensional convolution
layer, a batch normalization layer, a dense layer, and a 1-D maximum pooling
layer. We train the model using mean squared error loss on four different data
sets each with a different motif pattern randomly inserted in DNA sequences:
the first three data sets have zero, one, and two mutations applied on each
inserted motif, and the fourth data set represents the inserted motif as a
position-specific probability matrix. We use a novel proposed metric in order
to evaluate the model’s performance, $S_{\alpha}$, which is based on the
Jaccard Index. We use 10-fold cross validation to evaluate out model. Using
$S_{\alpha}$, we measure the accuracy of the model by identifying the 15
highest-scoring 15-mer indices of the predicted scores that agree with that of
the actual scores within a selected $\alpha$ region. For the best performing
data set, our results indicate on average 99.3% of the top 15 motifs were
identified correctly within a one base pair stride ($\alpha=1$) in the out of
sample data. To the best of our knowledge, this is a novel approach that
illustrates how data formatted in an intelligent way can be extrapolated using
machine learning.

###### Index Terms:

Motif Finding, Convolution Neural Network, Pairwise Sequence Alignment

##  I Introduction

Measuring the similarity of two sequences is a well known problem called
sequence alignment. This topic includes a vast category of methods for
identifying regions of high similarity in biological sequences, such as those
in deoxyribonucleic Acid (DNA), ribonucleic acid (RNA), and protein [7].
Specifically, DNA pairwise sequence alignment (PSA) methods are concerned with
finding the best arrangement of two DNA sequences. Some historically notable
dynamic programming PSA methods are the Needleman-Wunsch (NW) algorithm for
global alignment [1] and Smith-Waterman (SW) algorithm for local alignment
[2]. The main difference between global and local alignment is related to the
difference in length of the two sequences: global alignment attempts to find
the highest-scoring end-to-end alignment between two sequences of
approximately the same length, and local alignment searches for local regions
of high similarity between two sequences with different lengths [8]. Figure 1
shows this difference between local and global DNA alignment with two
sequences aligned in a 5’ (i.e. five prime) to 3’ direction. In molecular
biology, this orientation refers to the directionality of the carbon backbone
in DNA. The top subfigure displays global alignment where a query sequence is
aligned end-to-end with a reference. The bottom subfigure displays local
alignment where a short query sequence is most optimally aligned with a longer
reference sequence. This latter alignment displays how the query sequence is
approximately equal to a subsequence of the reference sequence.

Figure 1: Local vs. Global Alignment. In general, DNA is composed of a
permutation of the four nucleotides [adenine (A), thymine (T), cytosine (C),
guanine (G)] and an ambiguous base (N).

In this way, local alignment methods recognize approximate subsequence matches
of a query sequence with respect to a given reference sequence. One common
paradigm utilizing local alignment is to examine similarities between a query
sequence and specific k-long subsequences in a given gene, known as k-mers,
found within the reference sequence. Traditional local alignment algorithms
calculate these scores between the query sequence and each k-mer in the
reference sequence. The aim of this research is to identify where the most
likely subsequence matches of the query sequence occur in each reference
sequence using machine learning methods. One such type of query sequence that
is of high biological significance is a sequence motif, which are short
reoccurring subsequences of DNA [5]. Therefore, this research follows the
ability of machine learning methods to gauge the relative enrichment of
various representations of motifs (or motif patterns) in independent reference
sequences. More specifically, the efficacy of identifying motif enrichment in
sequences is explored using a one-dimensional (1-D) convolution neural network
(CNN).

Four different data sets are generated, each with a different motif pattern
randomly inserted in approximately 10,000 reference sequences: the first three
data sets have zero, one, and two mutations applied on each inserted motif,
and the fourth data set represents the inserted motif as a position-specific
probability matrix (PPM). In this data structure, each nucleotide position
corresponds to a frequency of nucleotides [22]. These distinct motif patterns
help display how the CNN model can recognize both subsequence matches with
exact, inexact, and probabilistic motifs. Each sample in a given data set
consists of artificial sequences enriched with a given motif pattern at a
frequency between five and fifteen occurrences per 1,000 base pairs (bp).
These samples are split into 986 overlapping 15-mers with a corresponding
calculated local alignment score from the BioPython Aligner [20]. These sores
are then predicted using a CNN with 10-fold cross validation. In order to
measure the performance of the model, the average out of sample mean squared
error (MSE), R2, and accuracy scores are reported.

While the MSE of the model trained on each data set is not representative of
the model’s effectiveness, the Jaccard Index and $S_{\alpha}$, a novel
modified version of the Jaccard Index, are better suited to capture accuracy
of the model. The standard MSE is not suitable for this problem because it
inherently only displays differences between predicted and actual values.
Since our aim is to locate those highest-scoring 15-mers, we need a metric
that determines at which positions they occur and with what accuracy (see
subsection V-A).  This new metric, $S_{\alpha}$, measures the degree of
similarity between two sets where each pair of elements can be different by at
most $\alpha$. Because of the plateauing nature of this metric as seen in each
data set and the risks involved in increasing alpha, only $S_{0}$ to $S_{5}$
are reported.

In implementing this new metric, the accuracy of the model increases
dramatically across all four data sets compared to the Jaccard Index. This
indicates that while the model is not able to precisely identify the highest-
scoring k-mers exactly, it is able to accurately identify their local region.
As expected, the model’s accuracy is far higher for the data sets with
relatively simple inserted motif patterns–non-probabilistic consensus
motifs–compared to that of the data set with more complex inserted motif
patterns, such as consensus PPM.

##  II Background

Clusters of motifs across a genome strongly correlate to a gene regulatory
regions [18]. These regions are especially important for motif enrichment
analysis, where known motifs are identified in the regulatory sequence of a
gene in order to determine which proteins (transcription factors and
enhancers) control its transcription [6] [19]. Motif enrichment analysis is
only relevant given that the regulatory region of a gene is known, otherwise
the sequence under study may be from a non-coding region of an organism’s
genome or an untranslated region of a gene [9]. Given that the regulatory
region of a gene is unknown, one frequently used approach to identifying it is
to first locate sequences enriched with highly conserved motifs. Fortunately,
many motifs that have been discovered are common amongst genes serving a
similar role across organisms, such as a negative regulatory region for
eukaryotes [10]. Finding these conserved motifs may facilitate the
identification of the regulatory regions in a gene. For that reason,
identifying the exact or relative positions of a given motif in a gene or
sequence is a relevant inquiry in the process for classifying candidate
regulatory regions of a gene.

A software toolkit known as MEME Suit includes three different methods for
motif-sequence searching [23]: FIMO (Find Individual Motif Occurrences) [21],
GLAM2SCAN (Gapped Local Alignment of Motifs SCAN) [24], and MAST (Motif
Alignment and Search Tool) [25].

FIMO focuses on scanning both DNA and protein sequences for a given motif
represented as PPM. This software tool calculates the log-likelihood ratio
score, p-value, and q-value (false discovery rate) for each subsequence
position in a sequence database [21].

Typically, GLAM2SCAN performs a Waterman-Eggert local alignment between motifs
found by GLAM2, its companion motif-finding algorithm, and a sequence
database. These local alignment scores are generated from an aligner
programmed with position specific residue scores, deletion scores, and
insertion scores returned from the GLAM2 algorithm. The $n$ highest alignments
are returned to the user [24].

MAST locates the highest-scoring $n$ subsequences with respect to a motif
described as a position-specific score matrix. Using the QFAST algorithm, MAST
calculates the p-value of a group of motif matches. This is accomplished by
first finding the p-value of each match (position p-value’) and normalizing it
for the length of the motif (’sequence p-value’). Then each of these
normalized p-values are multiplied together to find the statistical
significance across all located motifs in the database (’combined p-value’)
[25].

##  III Data Analysis & Curation

A single data set contains approximately 10,000 randomly generated DNA
sequences, each 1,000 bp long. The number of samples vary slightly from one to
another due to some inconsistencies that are removed in prepossessing. A
15-mer motif is inserted into each sample anywhere from five to fifteen times.
Four separate data sets of this structure are created where a different motif
pattern is inserted randomly into each sequence. The first three data sets
have zero, one, and two mutations applied on each inserted motif. These
mutations are applied in order to determine whether the proposed model has the
potential to identify consensus motifs and non-exact consensus motifs across
many sequences. Since motifs mostly exist as profiles where each base pair
position corresponds to a frequency table of nucleotides, the fourth data set
is created where the inserted motifs are based off of a PPM [11].

Equation 1 is used to calculate the PPM indicated by matrix $M$ given a set of
candidate motifs, or sequences that are thought to be from the same motif PPM.
This equation counts the number of occurrences of each nucleotide in set
$\gamma$ for each nucleotide position across all motifs, where
$\gamma=\\{A,T,C,G\\}$; $I=\\{0,1\\}$ represents an indicator function, where
$I(x=\gamma)$ is 1 if $x=\gamma$ and 0 otherwise; $i{\displaystyle\in}$ (1, …,
L), where L is the length of each motif; and $j{\displaystyle\in}(1,...,N)$,
where N is the number of motifs.

$M_{\alpha,k}=\frac{1}{N}\sum^{N}_{i=1}I(X_{i,j}=\gamma)$ (1)

In order to apply Equation 1 on candidate motifs, the DNA sequence data must
be formatted as nucleotide position counts shown in Figure 2. This figure
illustrates the conversion of a list of candidate motifs to matrix
$M_{counts}$ and then to $PPM$ using Equation 1. While Figure 2 displays this
process for five 10-mers, the fourth data sets in this work relies on profiles
built from ten 15-mers.

TACAGAGTTG

CCATAGGCGT

TGAACGCTAC

ACGGACGATA

CGAATTTACG

$\downarrow$

$M_{counts}$ =  A 1 1 3 3 2 1 0 2 1 1 T 2 0 0 1 1 1 1 2 2 1 C 2 2 1 0 1 1 1 1
1 1 G 0 2 1 1 1 2 3 0 1 2
$\downarrow$

$PPM$ =  A 0.2 0.2 0.6 0.6 0.4 0.2 0.0 0.4 0.2 0.2 T 0.4 0.0 0.0 0.2 0.2 0.2
0.2 0.4 0.4 0.2 C 0.4 0.4 0.2 0.0 0.2 0.2 0.2 0.2 0.2 0.2 G 0.0 0.4 0.2 0.2
0.2 0.4 0.6 0.0 0.2 0.4

Figure 2: The conversion of five candidate subsequence motifs to PPM using
Equation 1.

##  IV Feature & Output Selection

In order to format the sequence data into a structure that is both
recognizable and meaningful to a CNN, we first split each sequence into a list
of overlapping 15-mers. Next, we generate a one-hot encoding for each
nucleotide in the 15-mers. The resulting feature set is composed of 60 values.
Figure 3 displays this process using a small subsequence example formatted as
4-mers.

Figure 3: DNA subsequence k-mer formatting by one-hot encoding nucleotides.

To obtain the target values, each of these 15-mers are pairwise aligned with
the consensus motif for the given data set motif pattern using the SW
algorithm. Given two sequences, $a$ of length $n$ and $b$ of length $m$, this
algorithm begins by defining an $n+1$ by $m+1$ matrix $H$. The first column
and first row are assigned $0$, and the following recurrence relation is
applied to assign the rest of the values in $H$.

$H(i,j)=max\begin{cases}H(i-1,j-1)+\sigma(a_{i},b_{j})\\\ H(i,j-1)+W\\\
H(i-1,j)+W\\\ 0\end{cases}$

where W is a gap score and $\sigma$ is a score matrix such that

$\sigma(a_{i},b_{j})=\begin{cases}+1&\quad\text{if }a_{i}=b_{j}\\\
-2&\quad\text{if }a_{i}\neq b_{j}\end{cases}$

In the case when $a_{i}=b_{j}$, $\sigma$ returns a match score of $+1$, and in
the case when $a_{i}\neq b_{j}$, $\sigma$ returns a mismatch score of $-2$.
The gap score, $W$, is assigned $-2.5$. The match, mismatch, and gap score can
be configured for different alignments. These parameters are used because they
are the most optimal for this type of local alignment [4]. Once $H$ is
assigned its values, the best alignment is obtained by finding the maximum
value in $H$ and tracing back the matrix elements that led up to this maximum.
In this way, the maximum value in $H$ defines the optimal path in $H$ for the
best alignment between sequences $a$ and $b$ [2]. The calculated alignment
scores are normalized based on the maximum alignment score in each sample.

##  V Methods

###  V-A CNN Model Evaluation

Although the MSE loss function is effective at penalizing large differences
between predicted and target values, such as outliers in the data, it does not
successfully represent the predictive power of the model given the scope of
the problem [14]. In the data, the target value from each sample ranges from
zero to one. This range already generates an inherently small MSE. Even when
the MSE for each sample is normalized, the metric is overshadowed by the
overwhelming majority of the predicted values that were approximately equal to
the global mean of each sample. In other words, the MSE as a metric does not
capture the correct information pertaining to the five to fifteen inserted
motif patterns in each sample due to a large unequal distribution of such
scores that deviate from the global mean. This problem is analogous to that of
an unequal class distribution in a classification problem.

The goal of the model is to score the CNN based on its ability to locate the
15 highest-scoring 15-mers, because we inserted a motif pattern at most 15
times into a single sample. Since this network deals with continuous values
instead of discrete classes, initially we cannot be certain of the 15-mer to
which a 15-mer score at any index $i$ corresponds. However, a higher scoring
15-mer has a greater probability of corresponding to that of a motif, whereas
the lower scoring 15-mers carry little information. This is due to the fact
that each score in the data is generated from a local alignment between 15-mer
and the given consensus motif. In this way, only the highest 15-scoring
15-mers are of interest. As previously mentioned, we indicate that there is an
unequal distribution between the number of scores corresponding to that of
each inserted motif and the global mean of each sample. Using these
observations, we rationalize that we only have to examine the 15 highest-
scoring indices. This generality that the 15 highest-scoring idicies
correspond to the inserted motif patterns is further supported by the notion
that probability of observing a random 15-mer exactly equal or similar to the
inserted motifs is relatively low.

Thus, the indices of the predicted 15 highest-scoring 15-mer inherently hold
information about the position of possible inserted motif patterns because it
is at these indices at which the local alignment is conducted. Due to the low
likelihood of observing a false positive (when a 15-mer is identified as a
motif but in all actuality is not one), we create a one-to-one correspondence
between the indices of the actual motif indices and that of the predicted
motifs using high local alignment scores. The accuracy of this one-to-one
correspondence can be measured using the Jaccard Index given in Equation 2.

$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$ (2)

We propose a more generalized index, $S_{\alpha}$, in Equation 3 which
measures the similarity of two sets with an allowed margin of error of
$\alpha$. Because of the high locality of local alignment score predictions
and due to the fact that the highest-scoring 15-mers can still be found from
examining the immediate region of a prediction, this margin of error serves as
a heuristic for motif identification. In this metric, two items are considered
identical if they are no more than $\alpha$ away from each other. In the scope
of this work, sets $A$ and $B$ contain the indices of the 15 highest-scoring
15-mers of the actual data and predicted data, respectively. When $\alpha=0$,
$S_{0}(A,B)$ in Equation 2 is identical to $J(A,B)$ in Equation 3. Conversely,
as $\alpha$ increases, the allowed distance between indices in sets $A$ and
$B$ increases. For example, when $\alpha=2$, a predicted 15-mer index $i$ and
actual 15-mer index $i+2$ are considered the same.

$J(A,B\mid\alpha)=S_{\alpha}(A,B)=\frac{|\bigcup\limits_{\mu=0}^{\alpha}A\cap\\{x+\mu\mid
x\in B\\}|}{|A\cup B|}$ (3)

The following process is an algorithm to calculate a modified version of the
Jaccard Index. Using the $argsort$ function in NumPy, we examine the indices
that order both the actual outputs and the predicted outputs. In looping
through the each of the top $n$ indices of the predicted outputs, we count the
number of them which are contained in the list of indices of the actual
outputs. The process returns the score as count over the maximum possible
value, which in this case is $n$. This is implemented in Algorithm 1

Algorithm 1 Measuring Jaccard Index with stride $\alpha$

1:procedure $s_{\alpha}$

2: $\textit{n}\leftarrow\text{number of highest-scoring k-mers to analyze}$

3: $\textit{score}\leftarrow 0$

4: $\textit{act\\_outputs}\leftarrow\text{actual outputs}$

5: $\textit{pred\\_outputs}\leftarrow\text{outputs from CNN}$

6: $\textit{act\\_indxs}\leftarrow\text{indices that would sort
}\textit{act\\_outputs}$

7: $\textit{pred\\_indxs}\leftarrow\text{indices that would sort
}\textit{pred\\_outputs}$

8:  _outerloop_ :

9: for $i$ := 1 to $n$ do

10: $\textit{pred\\_indx}\leftarrow\textit{pred\\_indxs(i)}$.

11: for $j$ := 0 to $\alpha$ do

12: if $\textit{pred\\_indxs}\in\textit{act\\_indxs}-j$ then

13: $score\leftarrow score+1$.

14: goto _outerloop_.

15: if $\textit{pred\\_indxs}\in\textit{act\\_indxs}+j$ then

16: $score\leftarrow score+1$.

17: goto _outerloop_.

18: $normalized\\_score\leftarrow score/n$.

##  VI Results

Each of the four data sets is characterized by 10,000 samples where each
sample contains a sequence that is 1,000 bp in length. In each sample, a motif
pattern is inserted randomly anywhere from five to fifteen times. The first
three data sets include inserted motif patterns with zero, one, and two
mutations. The fourth data set includes an inserted motif pattern represented
based on a PPM. Each data set is evaluated using out of sample data generated
from 10-fold cross validation based on eight metrics: MSE, R2, and
$S_{0}$-$S_{5}$.

Table I: CNN Results. The average out of sample MSE, R2, and $S_{0}$-$S_{5}$
for each data set.

A fifth analysis is conducted with another data set using a motif
representation similar to that of the fourth data set with the MafK
transcription factor from the BATCH1 regulatory gene [26]. This motif is a
15-mer with a less conserved consensus sequence compared to that of the former
four data sets. While this data set did not perform as well as the other four
data sets with a $S_{9}$ of 45.3%, this analysis brought to light the
consideration of the aligner scoring matrix as another hyperparameter to this
work.

As it turns out, the performance of the model varies greatly with the chosen
match score, mismatch score penalty, and gap score penalty for the currently
implemented alignment method. For instance, the $S_{9}$ varies from 33.7% to
52.6% with different scoring hyperparameters. The former result is derived
from an aligner with a match score of +2.0, mismatch score penalty of -3.0,
and gap score penalty of -3.5, whereas the latter result is derived from an
aligner with a match score of +2.0, mismatch score penalty of -4.0, and gap
score penalty of -4.5. It is currently unclear what aligner hyperparameters
are most optimal for this more complex data set and the original four data
sets explored in the work. Although there is evidence to suggest that aligner
scoring matrices vary with the type of inserted motif pattern, it is unclear
whether the most optimal hyperparameters change from motif to motif.

One possible interpretation of the dependence of the model’s chosen evaluation
metric, $S_{\alpha}$, on the aligner hyperparameters is related to the fact
that the CNN predicts alignment scores that are normalized within each sample.
Therefore, the farther these highest-scoring scores are from the global mean,
the more likely that the proposed metric will be able to recognize inserted
motifs. Conversely, when analyzing a data set with a less conserved motif
consensus sequence, such as that of the MafK transcription factor, the
alignment scores are closer to the global mean of each sample. This in turn
makes recognizing the indices of the highest-scoring segments more
challenging. It follows that the aligner hyperparameters which capitalize on
increasing this difference are most favorable for all motifs, regardless of
pattern.

###  VI-A Convolution Neural Network (CNN) Architecture

CNN is a class of deep learning models which can infer patterns based on data
formatted as a grid structure, such as a set of prices over time for stock or
a grid representation of pixels in an image (add reference for these
architectures). These Artificial Neural Netowrk (ANNs) use a linear
mathematical operation called convolution in at least one of their layers [3].
The convolution operation is commonly identified by the following two
equations:

$s(t)=\int x(a)w(t-a)da$ (4)

$s(t)=(x*w)(t)$ (5)

Equation 4 explicitly denotes the equation for convolution, whereas Equation 5
displays how an asterisk can be used to for the linear operation. In both
equations, $x$ is referred to as the input. Typically, this is formatted as a
multidimensional array, or a tensor, that matches the size and dimensions of
the data. The second argument is $w$, representing a kernel, which stores
parameters for the model also formatted as a tensor. This argument is adapted
throughout the training process of the model. The output of both functions,
$s$, is called the feature map of the convolution layer. This is what is fed
into the next layer of the network [3]. Hidden layers are generated from
applying a kernel, or filter, of weights over the receptive field of the
inputs. More specifically, the hidden layer is computed based off of the
filter weights and the input layer as it strides across the feature space
[28]. This operation can either compress or expand input space depending on
the applied kernel [29]. This paradigm is followed by rounds of activations,
normalizations, and pooling [29]. The model typically ends with a fully
connected layer to compute its outputs [28]. The proposed model is represented
in Figure 4 [cite my paper].

Figure 4: CNN model. (create better caption)

The model is marked by three rounds of a 1-D convolution layer, a batch
normalization layer, a dense layer, and a 1-D maximum pooling layer. After
these 12 layers, the model finishes off with a 50% dropout layer, a flattened
layer, and finally a fully connected layer corresponding to the 986 alignment
scores for each sample [13] [12].

The model described above is ran on all four data sets for 100 epochs with a
batch size of 80 and compiled with the Adam optimizer (learning rate=0.001,
beta 1=0.9, beta 2=0.999, epsilon=1e-07). Of the 10,000 samples in each
dataset, 80% is reserved for training the network and the remaining 20% is
used for validation after each epoch. For its loss function, the model relies
on Mean Squared Error (MSE), which is calculated between predicted values
($y_{pred}$) and target values ($y_{act}$) with the following formula in
Equation 6:

$MSE(y_{pred},y_{act})=\frac{1}{n}\sum_{i=1}^{n}(y_{pred,i}-y_{act,i})$ (6)

##  VII Discussion

As displayed in this work, deep learning models, such as a CNN, have the
capacity to recognize and predict the positions of an inserted motif with
great accuracy. Furthermore, data structures can be devised to take advantage
of unequal class distributions in regression problems as highlighted by the
design of k-mer data representation in this work and the incorporation of
$S_{\alpha}$ as a novel evaluation metric.

In analyzing the results in Table I, there is a characteristic pattern between
the accuracy metrics across each data set. For instance, in comparing
$S_{0}$-$S_{5}$ for the first data set with zero mutations applied on each
inserted motif, the score monotonically increases with an increasing $\alpha$.
This is evident for the three other data sets as well. With respect to this
particular trend, it is expected that as $\alpha$ increases, the score will
also increase since $\alpha$ relates directly to the allowed margin of error,
making $S_{\alpha}$ less conservative.

Additionally, the model’s accuracy is far higher for the data sets with
relatively simple inserted motif patterns, such as nonmutated and mutated
consensus motifs, compared to that of the fourth data set with a PPM motif
pattern. This relationship can be explained by the process by which the scores
for each 15-mer are calculated. For a given 15-mer, a score is computed based
on its local alignment with a given consensus motif. For the first data set,
these local alignment scores generated are derived from each inserted motif,
whereas in the latter three data sets, the scores are not necessarily derived
from each data set’s consensus motif since the motif patterns support variable
inserted motif.

In all data sets, the largest increase in $S_{\alpha}$ appears to be between
the $S_{0}$ and $S_{1}$. After this point, change in $S_{\alpha}$ plateaus
after a given $\alpha$. With the consideration that the likelihood of
observing a false positive is relatively low, this indicates that the addition
of stride $\alpha$ is well-advised. This is the case because the increase in
$\alpha$ only influences $S_{\alpha}$ up to a certain point. It is expected
that as $\alpha\xrightarrow{}\beta$, where $\beta$ is the maximum $\alpha$ on
either side of a given motif index, $S_{\alpha}\xrightarrow{}1$ because every
single $n$ indices will be covered by the stride ${\alpha}$. In the case that
$S_{\alpha}\xrightarrow{}1$, the certainty for each identified motif decreases
with increasing $S_{\alpha}$ regardless; however, the absence of this limit in
the data indicates that the certainty of the identified motifs does not
decreases dramatically from $S_{0}$ to $S_{5}$. Furthermore, the presence of a
plateauing $S_{\alpha}$ supports the thought that a decrease in the certainty
of an identified motif is negligible. This analysis can be drawn further in
noticing that the point at which $S_{\alpha}$ plateaus increases as the
complexity of the motif pattern increases. In the case of a more complex motif
pattern, such as either of the PPMs, a greater $\alpha$ is required to fully
encapsulate accuracy of the model’s predictions. Even then, the certainty of
such motif identification with increasing $\alpha$ decreases.

In subsection V-A, we draw a one to one correspondence between the actual
motif indices and that of the predicted motifs by only examining the indices
of the 15 highest-scoring 15-mers in both the actual scores and predicted
scores. This is not a strong one-to-one correspondence because the number of
inserted motifs actually varies randomly from five to fifteen times sample to
sample. By design, this is a confounding variable When $S_{\alpha}$ is applied
on a sample with five inserted motifs, the returned score is predicted to be
an underestimate of the model’s prediction. This is due to the fact that this
function only examines the highest 15-scoring indices for each sample. In the
case of five inserted motifs, there would be ten 15-mers identified as high-
scoring motifs, when in reality these are random 15-mers in the sequence.
Because those scores are more likely to be present throughout a sequence,
there will be less similarity between the indices of the predicted 15 highest-
scoring 15-mers and that of the actual 15 highest-scoring 15-mers. This will
most likely lead to a decrease in $S_{\alpha}$.

## References

  * [1] Cold Spr.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  Mol. Biol, 48:443–153, 1970.
  * [2] Temple F Smith, Michael S Waterman, et al.  Identification of common molecular subsequences.  Journal of molecular biology, 147(1):195–197, 1981.
  * [3] Yoshua Bengio, Ian Goodfellow, and Aaron Courville.  Deep learning, volume 1.  MIT press Massachusetts, USA:, 2017.
  * [4] Ahmad Al Kawam, Sunil Khatri, and Aniruddha Datta.  A survey of software and hardware approaches to performing read alignment in next generation sequencing.  IEEE/ACM transactions on computational biology and bioinformatics, 14(6):1202–1213, 2016.
  * [5] Patrik D’haeseleer.  What are dna sequence motifs?  Nature biotechnology, 24(4):423–425, 2006.
  * [6] Robert C McLeay and Timothy L Bailey.  Motif enrichment analysis: a unified framework and an evaluation on chip data.  BMC bioinformatics, 11(1):165, 2010.
  * [7] Waqar Haque, Alex Aravind, and Bharath Reddy.  Pairwise sequence alignment algorithms: A survey.  In Proceedings of the 2009 Conference on Information Science, Technology and Applications, page 96–103, 2009.
  * [8] EMBL-EBI.  Pairwise Sequence Alignment, 2020.
  * [9] Xiaole Liu, Douglas L Brutlag, and Jun S Liu.  Bioprospector: discovering conserved dna motifs in upstream regulatory regions of co-expressed genes.  In Biocomputing 2001, pages 127–138. World Scientific, 2000.
  * [10] Jorge A Iñiguez-Lluhí and David Pearce.  A common motif within the negative regulatory regions of multiple factors inhibits their transcriptional synergy.  Molecular and Cellular Biology, 20(16):6040–6050, 2000.
  * [11] Modan K Das and Ho-Kwok Dai.  A survey of dna motif finding algorithms.  In BMC bioinformatics, volume 8, page S21. Springer, 2007.
  * [12] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  Nature, 521(7553):436–444, 2015.
  * [13] Jürgen Schmidhuber.  Deep learning in neural networks: An overview.  Neural Networks, 61:85–117, 2015.
  * [14] Yu Qi, Yueming Wang, Xiaoxiang Zheng, and Zhaohui Wu.  Robust feature learning by stacked autoencoder with maximum correntropy criterion.  In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6716–6720. IEEE, 2014.
  * [15] Luping Ji, Xiaorong Pu, Hong Qu, and Guisong Liu.  One-dimensional pairwise cnn for the global alignment of two dna sequences.  Neurocomputing, 149:505–514, 2015.
  * [16] Q. Zhang, L. Zhu, W. Bao, and D. Huang.  Weakly-supervised convolutional neural network architecture for predicting protein-dna binding.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 17(2):679–689, 2020.
  * [17] Gary D Stormo and George W Hartzell.  Identifying protein-binding sites from unaligned dna fragments.  Proceedings of the National Academy of Sciences, 86(4):1183–1187, 1989.
  * [18] Martin C. Frith, Michael C. Li, and Zhiping Weng.  Cluster-Buster: finding dense clusters of motifs in DNA sequences.  Nucleic Acids Research, 31(13):3666–3668, 07 2003.
  * [19] Tom Lesluyes, James Johnson, Philip Machanick, and Timothy L. Bailey.  Differential motif enrichment analysis of paired chip-seq experiments.  BMC Genomics, 15(1):752, 2014.
  * [20] Peter J. A. Cock, Tiago Antao, Jeffrey T. Chang, Brad A. Chapman, Cymon J. Cox, Andrew Dalke, Iddo Friedberg, Thomas Hamelryck, Frank Kauff, Bartek Wilczynski, and Michiel J. L. de Hoon.  Biopython: freely available python tools for computational molecular biology and bioinformatics.  Bioinformatics, 25(11):1422–1423, 8/5/2020 2009.
  * [21] Charles E. Grant, Timothy L. Bailey, and William Stafford Noble.  Fimo: scanning for occurrences of a given motif.  Bioinformatics, 27(7):1017–1018, 9/8/2020 2011.
  * [22] Mengchi Wang, David Wang, Kai Zhang, Vu Ngo, Shicai Fan, and Wei Wang.  Motto: Representing motifs in consensus sequences with minimum information loss.  Genetics, page genetics.303597.2020, 08 2020.
  * [23] Timothy L. Bailey, Mikael Boden, Fabian A. Buske, Martin Frith, Charles E. Grant, Luca Clementi, Jingyuan Ren, Wilfred W. Li, and William S. Noble.  Meme suite: tools for motif discovery and searching.  Nucleic Acids Research, 37(suppl_2):W202–W208, 9/9/2020 2009\.
  * [24] Martin C. Frith, Neil F. W. Saunders, Bostjan Kobe, and Timothy L. Bailey.  Discovering sequence motifs with arbitrary insertions and deletions.  PLOS Computational Biology, 4(5):e1000071–, 05 2008.
  * [25] T L Bailey and M Gribskov.  Combining evidence using p-values: application to sequence homology searches.  Bioinformatics, 14(1):48–54, 9/9/2020 1998.
  * [26] Oriol Fornes, Jaime A Castro-Mondragon, Aziz Khan, Robin van der Lee, Xi Zhang, Phillip A Richmond, Bhavi P Modi, Solenne Correard, Marius Gheorghe, Damir Baranašić, Walter Santana-Garcia, Ge Tan, Jeanne Chèneby, Benoit Ballester, François Parcy, Albin Sandelin, Boris Lenhard, Wyeth W Wasserman, and Anthony Mathelier.  JASPAR 2020: update of the open-access database of transcription factor binding profiles.  Nucleic Acids Research, 48(D1):D87–D92, 11 2019.
  * [27] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep Learning.  MIT Press, 2016.
  * [28] Jürgen Schmidhuber.  Deep learning in neural networks: An overview.  Neural Networks, 61:85–117, 2015.
  * [29] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  Nature, 521(7553):436–444, 2015.
  * [30] Ethan J Moyer and Anup Das.  Machine learning applications to dna subsequence and restriction site analysis.  arXiv preprint arXiv:2011.03544, 2020.


Table 12: Benchmarking information retrieval recall@1/5/10 on M-BEIR for CLIP
Base models. For Fashion200K and FashionIQ, we report recall@10/20/50
following the original work.

|  |  | Multi-task (✗ instruction) | UniIR (✓instruction)
---|---|---|---|---
|  |  |  BLIP${}_{\text{SF}}$ |  BLIP${}_{\text{FF}}$ |  BLIP${}_{\text{SF}}$ |  BLIP${}_{\text{FF}}$
| Dataset | Metric |  M-BEIR${}_{\text{local}}$ | M-BEIR |  M-BEIR${}_{\text{local}}$ | M-BEIR |  M-BEIR${}_{\text{local}}$ | M-BEIR |  M-BEIR${}_{\text{local}}$ | M-BEIR
1\. $q_{t}\to c_{i}$ |  | R@1 | 7.1 | 0.0 | 7.8 | 0.0 | 6.9 | 5.5 | 7.5 | 6.9
VisualNews | R@5 | 16.9 | 2.3 | 18.2 | 3.4 | 17.0 | 15.9 | 18.0 | 17.6
| R@10 | 22.9 | 5.0 | 24.3 | 6.9 | 22.8 | 21.9 | 24.3 | 23.8
| R@1 | 47.3 | 0.0 | 48.1 | 0.0 | 47.8 | 11.3 | 49.5 | 23.8
MSCOCO | R@5 | 74.6 | 15.4 | 75.7 | 10.5 | 75.6 | 65.1 | 76.6 | 70.2
| R@10 | 83.4 | 32.9 | 84.5 | 24.4 | 84.5 | 76.5 | 85.1 | 80.2
| R@10 | 22.1 | 3.5 | 22.3 | 0.9 | 21.6 | 21.2 | 22.8 | 22.1
Fashion200K | R@20 | 29.7 | 7.5 | 29.6 | 3.0 | 28.2 | 27.8 | 30.6 | 30.3
| R@50 | 42.5 | 18.2 | 41.8 | 8.7 | 40.0 | 39.7 | 41.5 | 41.1
2\. $q_{t}\to c_{t}$ |  | R@1 | 50.1 | 47.9 | 49.2 | 46.9 | 51.4 | 51.2 | 50.1 | 49.7
WebQA | R@5 | 77.0 | 74.2 | 76.2 | 74.6 | 76.7 | 76.7 | 76.4 | 76.4
| R@10 | 84.0 | 82.0 | 83.4 | 81.9 | 83.3 | 83.2 | 82.7 | 82.7
3\. $q_{t}\to$ ($c_{i},c_{t}$) |  | R@1 | 20.7 | 12.0 | 23.8 | 12.2 | 22.0 | 21.2 | 23.5 | 22.6
EDIS | R@5 | 40.2 | 30.0 | 47.5 | 30.4 | 44.5 | 44.1 | 46.2 | 45.9
| R@10 | 50.1 | 38.7 | 57.7 | 38.9 | 53.9 | 53.7 | 56.7 | 56.4
| R@1 | 49.0 | 45.0 | 49.1 | 45.7 | 49.9 | 49.6 | 49.5 | 49.1
WebQA | R@5 | 77.3 | 73.5 | 78.1 | 75.0 | 77.5 | 77.2 | 78.1 | 77.9
| R@10 | 86.6 | 83.4 | 85.9 | 82.6 | 86.4 | 86.2 | 85.6 | 85.5
4\. $q_{i}\to c_{t}$ |  | R@1 | 7.1 | 0.0 | 7.4 | 0.0 | 6.6 | 3.7 | 7.2 | 5.0
VisualNews | R@5 | 17.1 | 3.2 | 17.1 | 2.3 | 16.8 | 14.8 | 17.1 | 15.8
| R@10 | 23.2 | 6.7 | 22.8 | 5.0 | 22.6 | 21.4 | 23.6 | 22.5
| R@1 | 58.3 | 0.0 | 63.7 | 0.0 | 62.4 | 39.2 | 64.6 | 51.7
MSCOCO | R@5 | 83.0 | 71.6 | 87.0 | 71.7 | 85.9 | 84.5 | 88.1 | 86.9
| R@10 | 90.3 | 83.3 | 93.1 | 83.9 | 92.0 | 91.5 | 93.5 | 93.1
| R@10 | 22.4 | 1.6 | 23.6 | 0.9 | 20.9 | 18.2 | 23.8 | 22.4
Fashion200K | R@20 | 30.4 | 4.0 | 32.0 | 2.4 | 29.7 | 27.7 | 32.7 | 31.5
| R@50 | 43.8 | 10.2 | 44.7 | 6.8 | 42.3 | 40.6 | 45.6 | 45.1
5\. $q_{i}\to c_{i}$ |  | R@1 | 8.2 | 8.2 | 8.0 | 8.0 | 7.7 | 7.7 | 7.7 | 7.7
NIGHTS | R@5 | 30.0 | 29.7 | 31.8 | 31.6 | 30.7 | 30.6 | 30.3 | 30.3
| R@10 | 49.8 | 49.1 | 51.0 | 50.5 | 51.2 | 51.2 | 49.5 | 49.5
6\. ($q_{i},q_{t}$) $\to c_{t}$ |  | R@1 | 17.6 | 16.9 | 19.6 | 20.4 | 13.9 | 16.0 | 17.9 | 20.8
OVEN | R@5 | 33.2 | 29.2 | 36.7 | 32.8 | 28.9 | 28.2 | 34.5 | 33.1
| R@10 | 40.7 | 35.2 | 44.4 | 38.9 | 36.1 | 34.1 | 42.1 | 39.0
| R@1 | 7.6 | 3.7 | 8.6 | 5.6 | 6.3 | 5.0 | 7.9 | 6.9
InfoSeek | R@5 | 17.3 | 9.5 | 21.2 | 13.6 | 16.5 | 13.3 | 18.9 | 16.5
| R@10 | 23.6 | 14.0 | 28.1 | 19.3 | 23.3 | 19.6 | 25.4 | 22.5
7\. ($q_{i},q_{t}$) $\to c_{i}$ |  | R@10 | 22.5 | 22.1 | 25.4 | 24.9 | 20.8 | 20.1 | 23.7 | 23.0
FashionIQ | R@20 | 29.9 | 29.2 | 33.2 | 32.5 | 27.5 | 26.6 | 31.0 | 29.8
| R@50 | 41.2 | 40.3 | 44.8 | 43.9 | 38.2 | 36.6 | 42.1 | 40.5
| R@1 | 11.0 | 9.1 | 20.3 | 18.7 | 13.1 | 12.9 | 20.2 | 19.4
CIRR | R@5 | 39.0 | 31.8 | 45.1 | 42.0 | 42.2 | 40.7 | 46.4 | 45.1
| R@10 | 50.3 | 42.7 | 56.0 | 52.2 | 54.4 | 52.3 | 57.5 | 55.8
8\. ($q_{i},q_{t}$) $\to$ ($c_{i},c_{t}$) |  | R@1 | 28.3 | 32.5 | 31.1 | 33.2 | 28.3 | 33.0 | 29.1 | 37.1
OVEN | R@5 | 47.0 | 46.8 | 49.9 | 47.5 | 47.3 | 48.2 | 48.2 | 50.6
| R@10 | 54.6 | 52.5 | 57.5 | 53.1 | 54.7 | 54.2 | 55.6 | 55.9
| R@1 | 11.2 | 9.4 | 13.7 | 10.9 | 12.2 | 10.8 | 13.0 | 11.8
InfoSeek | R@5 | 25.5 | 20.7 | 29.1 | 22.7 | 26.4 | 23.6 | 27.0 | 23.5
| R@10 | 33.6 | 27.9 | 37.3 | 29.4 | 34.2 | 30.7 | 35.0 | 30.4
- |  | R@1 | 24.9 | 14.2 | 26.9 | 15.5 | 25.3 | 20.6 | 26.8 | 24.1
Average | R@5 | 44.5 | 33.7 | 47.2 | 35.2 | 45.1 | 43.3 | 46.6 | 45.4
| R@10 | 47.5 | 36.3 | 49.8 | 37.1 | 47.7 | 46.0 | 49.2 | 47.8

Table 13: Benchmarking information retrieval recall@1/5/10 on M-BEIR for BLIP
Base models. For Fashion200K and FashionIQ, we report recall@10/20/50
following the original work.