\chapter{The Artificial Chemistry}
\label{TheAC}
We present our Artificial Chemistry (AC) called the Molecular Classifier System (\MCS) which is derived from the Holland broadcast language (BL). This evolutionary simulation platform is implemented as an agent-based system in which the agents are artificial molecules. Chemical reactions between the artificial molecular species refer to the interactions between agents. In this chapter, we introduce our motivations for utilising the \MCS. We then present the class of Molecular Classifier Systems and our implementation of the Holland broadcast language. We finally describe the system's algorithm and summarise this chapter.

\section{Motivations}
In chapter \ref{modellingCSNs}, we concluded that algebraic and agent-based frameworks provide most flexibility. Because of their discrete composition of structural entities, they can act at different levels of abstraction ranging from sub-molecular interactions up to summarised system global function. Moreover, introducing analytical or stochastic information is enabled through the use of transformation techniques. Based on this review we propose to use an agent-based approach in which agents (molecular species) and interactions (chemical reactions) are modelled as algebraic expressions.

In chapter \ref{evolvingACSNs}, we argued that bottom-up evolutionary approaches (i.e., Artificial Chemistries) offer the most adequate framework to study the evolution of molecular organisations. These systems, \textit{a contrario} to top-down approaches, do not rely on explicitly defined fitness functions which may stifle the occurrence of ``perpetual novelty'' during evolution  \citep{860359}. Furthermore ACs are commonly implemented as agent-based systems, these approaches may thus benefit from the advantages, as highlighted earlier, of agent-based modelling techniques. Therefore we propose to employ an agent-based AC to model \textit{and} evolve artificial molecular organisations. 

To specify the molecular species and reactions, we employ the broadcast language. The latter is a term rewriting system which was proposed by Holland but has never been implemented nor evaluated (Section \ref{sectionBLreview}). The benefits of using the broadcast language here are twofold:
\begin{enumerate}
	\item The broadcast language, being a term-rewriting approach, provides a flexible modelling tool addressing the discrete and reflexive nature of molecular species. The development of complementary tools enables the translation of BL models to the SBML format. Through the use of this standard format, it is possible to transform the BL models into ODE systems, which allows us to conduct further analytical studies and make the generated models widely accessible.
	\item We provide the first implementation and evaluation of the broadcast language. This study complements the proposal originally made by Holland in the mid-seventies \citep{holland1992ana}. Our implementation may also provide a starting point for conducting further studies in allied areas such as in Evolutionary Computation and Genetic Programming.
\end{enumerate}

The above points suggest that the BL is a suitable modelling technique to be utilised in our investigation. However the original Holland broadcast language contained a number of features which posed some semantic ambiguities \citep{ALL-06-01}. To facilitate our investigation, we propose a simplification of the broadcast language in which we remove the problematic features \citep{DBLP:conf/eurogp/DecraeneMMK07}. These system modifications are summarised in Appendix \ref{app:bl}.  

Finally to address the stochastic nature of molecular reactions, we integrate the BL within the Molecular Classifier System (MCS) approach, a class of string-rewriting based ACs. In keeping with the conclusions of our literature review, we propose an agent-based AC where the agents and interactions are specified in the broadcast language. This novel AC is derived from the MCS and (simplified) BL formalisms which are both now presented.

\section{The Molecular Classifier Systems}
We define the Molecular Classifier System (MCS) as a class of string-rewriting based Artificial Chemistries. This approach is inspired by Holland's Learning Classifier Systems (LCS). Both the MCS and LCS formalisms rely on the \ttfamily IF THEN \normalfont metaphor: \ttfamily IF \normalfont a condition is satisfied (e.g., some molecules collide and bind with each other) \ttfamily THEN \normalfont  an action is executed (e.g., a product molecule is generated). In LCS, a demarcation is distinguished between \textit{rules} and \textit{messages}, however operations in biochemical networks are intrinsically \emph{reflexive} in the sense that all molecules can function as both rules (enzymes) and messages (substrates). The MCS addresses these issues by removing this rule/message demarcation found in the LCS.

The behaviour of the condition/binding properties and action/enzymatic functions is specified by a ``chemical" language defined in the MCS. The chemical language defines and constrains the complexity of the chemical reactions that may be represented and simulated with the MCS. For example, a MCS model using a limited number of computational functions may only faithfully represent very simplistic chemical reactions.

Before describing the nature of the enzymatic functions (action part of a molecule), the binding properties of the molecules must be identified. In the MCS approach, a reaction between molecules may only occur if the informational string of a substrate molecule satisfies/binds with the conditional part (``binding site'') of an enzyme molecule. The condition part refers to the binding properties of a molecule whereas action refers to the computational (``enzymatic") function. This pattern  matching implies a notion of \textit{binding specificity}. A molecule's binding site having a high specificity would significantly limit the range of molecular species that may bind to it. Whereas a greater range of species would bind to binding sites exhibiting low specificity. 

Reactions initially occur within a single reactor whose carrying capacity is limited (i.e., a reactor may contain a fixed maximum number of $n_{max}$ molecules). When two molecules can bind and consequently react with each other, the action part of one of the molecules is used to carry out the enzymatic operations upon the binding molecule (substrate). The symbols contained in the MCS action part are processed in a sequential order (parsed from left to right). This operation results in producing an offspring molecule whose nature depends on the symbols' functionality. This is analogous to the action part of a LCS rule used by Holland \citep{holland2001eec}. 

When a successful catalytic reaction occurs, a product species is inserted into the reactor. If the latter is full (i.e., if the reactor contains $n_{max}$ molecules) then a molecule is selected at random (other than the reactants) and removed from the reactor. Moreover all reactants are catalytic in the sense that they are not consumed during reactions.

A differing implementation of the MCS was proposed to investigate protocell computation \citep{mcmullin07}. In that study, a protocell is modelled as a container for artificial molecules. The latter may interact with each other to generate new molecular offspring. The chemical language used in that instance of the MCS employs a minimal set of computational components which only allows the modelling of replicase molecules. To represent, simulate and evolve CIPNs, more computational functions are necessary. To allow a richer repertoire of chemical reactions, we employ here a simplification of the Holland BL to specify and model the artificial molecular species and reactions. In the remainder of this chapter, we first present some system features which are generic to the MCS. Following this, our version of the BL and the \MCS~system are described.

\subsection{The single reactor model}
\label{subsec:singleReacMod}
In the MCS class, the alphabet of the employed chemical language is denoted by $\Lambda$. $S=\{s_1, \ldots, s_i, \ldots, s_\alpha\}$ is the set of strings (with string length $L$ and a maximal fixed length $Lmax$) over $\Lambda$, $\alpha=\sum_{L=1}^{Lmax}|\Lambda|^L$. $S$ also constitutes the set of all possible molecular species that may appear in the MCS. $R=\{r_1, \ldots, r_j, \ldots, r_\beta\}$ is the set of all reactions that may occur between molecular species $s_i \in S$, $\beta \leq \alpha^2$ with $\alpha^2$ being the total number of species-pair combinations. Chemical reactions are bimolecular (i.e., involve the interaction of two distinct molecules) and are noted as follows:
 
\begin{equation}
r_j=\ x\ +\ y \rightarrow z
\label{eqreaction}
\end{equation}

Eq. \ref{eqreaction} depicts an example reaction $r_j$ where $x,y$ and $z$ are molecular species in $S$. In this notation, the \textit{order} of the reactants is considered, i.e., the first term $x$ always designates an active broadcast device species (enzyme), the second term $y$ an input broadcast device species (substrate molecule) and $z$ an output broadcast device species (product molecule).

Chemical reactions are asymmetric in the sense that commuting $x$ and $y$ designates a different reaction, for example:
\begin{eqnarray}
r_1&=&\ s_1\ +\ s_2 \rightarrow s_3\label{eqreactionA}\\
r_2&=&\ s_2\ +\ s_1 \rightarrow s_4\label{eqreactionB}
\end{eqnarray}

$r_1$ and $r_2$ are two distinct chemical reactions, where $s_1$ is employed as an enzyme and $s_2$ as a substrate in Eq.~\ref{eqreactionA}. Whereas in Eq.~\ref{eqreactionB}, $s_2$ is utilised as an enzyme and $s_1$ is the substrate. $s_3$ and $s_4$ are two different product species.

\begin{equation}
r'_j=\ x\ +\ y \rightarrow \emptyset
\label{eqreactionC}
\end{equation}

Eq. \ref{eqreactionC} describes an example elastic reaction  (i.e., a reaction which does not lead to the production of an output broadcast device).


The system's state $U$ can be described by its finite collection of molecular instances denoted by $m_k$ at time $t$. For example $U(t) = (m_1, \ldots, m_k, \ldots, m_{n_{max}})$ describes the list of molecules occurring in $U$ at time step $t$, $n_{max}$ is finite. A distinct/molecule of the species class $s_i$ is denoted by $m_k^i$. Multiple molecules which are syntactically identical belong to the same molecular species class.

All molecules are contained in a single reactor in which they are ``competing'' with each other. Reactions result from successful molecular interactions which occur at random. During these random molecular collisions, two molecules $m_e$ and $m_s$ are identified where $m_e$ is treated as the enzyme molecule and $m_s$ as the substrate molecule.

If $m_e$ can bind/react with $m_s$ then a reaction successfully occurs: A product molecule $m_p$ is inserted in the reactor whereas another molecule $m_x$ (where $x\neq e \wedge x\neq s$) selected at random is removed from the reactor space (designating the system outflow).  In a MCS simulation, reactions may thus be described as follows:

\[
m_e\ +\ m_s\ +\ m_x\ \rightarrow m_e\ +\ m_s +\ m_p
\]

Figure \ref{fig:MCSflowchartA} depicts the flow of a MCS simulation.

\begin{figure}
	\centering
		\includegraphics[scale=1.4]{chapter4/flowchartA.eps}
	\caption{Program flow of a MCS simulation}	
	\label{fig:MCSflowchartA}
\end{figure}

This single reactor model was inspired by the Alchemy system in which a similar approach was employed.

\subsection{Mutation}
\label{sec:evoOpDesc}
We define the different operators which allow molecular variations to occur in the MCS. Two types of ``mutation'' are identified: 
\
\begin{enumerate}
	\item \textit{Molecular mutations}:
			\begin{itemize}
			\item When a new molecule is produced, a mutation is applied with probability $p_{sym}$ to each of its
			  symbols. Therefore, the longer the molecule, the higher the probability of one or more mutations occurring.  
			 	\item Three subtypes of molecular mutation are distinguished and are applied with equal probabilities at each symbol position:
				  \begin{itemize}
				  \item \emph{Symbol flipping:} The current symbol is replaced with a symbol picked uniformly at random from $\Lambda$ in which the current symbol is excluded.
				  \item \emph{Symbol insertion:} A symbol is picked uniformly at random from $\Lambda$ and inserted after the current symbol.
				  \item \emph{Symbol deletion:} The current symbol is removed.
				 \end{itemize}
			\end{itemize}
	\item \textit{Spontaneous mutations}:
		To maintain diversity in the event of low ongoing reaction activity, a spontaneous mutation mechanism occurring every $x$ timesteps is also available. A subset $r_{mut}$ of the population is selected at random and one of the three types of mutation mutation (chosen as above) is then applied to a single symbol picked uniformly at random in each molecule of this subset.
\end{enumerate}

\section{The broadcast language}
Prior to the development of the \MCS, we investigated the original broadcast language proposed by Holland\footnote{The broadcast language is a programming formalism devised by Holland in 1975, which aimed at allowing Genetic Algorithms (GAs) to use an \textit{adaptable representation}. A GA may provide an efficient method for adaptation but still depends on the efficiency of the fitness function used. During long-term evolution, this efficiency could be limited by the fixed representation used by the GA to encode the problem. When a fitness function is very complex, it may be desirable to adapt the problem representation employed by the fitness function. By adapting the representation, the broadcast language intended to overcome the deficiencies caused by fixed problem representation in GAs.}. As no implementation of the broadcast language was publicly available, we proposed the first complete specification and implementation of this formalism \citep{ALL-06-01}. Using this system, we successfully constructed a NAND gate \citep{decraene2007eac} and a static Genetic Regulatory Network model \citep{DBLP:conf/eurogp/DecraeneMMK07}. In the remainder of this section we present our simplified version of the broadcast language which is utilised to specify the molecular species and reactions in our agent-based Artificial Chemistry.

\subsection{Introduction}
We present our simplification of the Holland broadcast language. Artificial molecules (broadcast language strings) are referred to as broadcast devices, see Figure \ref{fig:bd}. A broadcast device is parsed into zero, one or more broadcast units, where each unit represents a single condition/action rule. When an action statement is executed, a new molecule is generated or ``broadcast'' in the reaction space. A broadcast device containing no broadcast units is called a null broadcast device and can function only as a substrate molecule (i.e., possessing no enzymatic/computational functions). 

\begin{figure}[htbp]
	\centering
		\includegraphics[scale=1.2]{chapter4/bd.eps}
	\caption{An example broadcast device}
	\label{fig:bd}
\end{figure}

Whenever a broadcast unit conditional statement is satisfied, the action statement is executed. This is analogous to an enzyme which would form a product molecule upon the binding of a specific substrate molecule to its binding region. In this metaphor the active site (where catalysis occurs) of the enzyme can be thought of as a broadcast unit, a substrate molecule would be a binding/input broadcast device, the active site's binding region would refer to the broadcast unit conditional statement, the product molecule is the output broadcast device and finally the environment would be the reaction space (e.g., the cell). Figure \ref{fig:bdReaction} depicts an example chemical reaction in the BL.

\begin{figure}[htbp]
	\centering
		\includegraphics[scale=1.3]{chapter4/bdReaction.eps}
	\caption{Example reaction}
	\label{fig:bdReaction}
\end{figure}

Some broadcast units may generate an output broadcast device that may itself contain zero, one or more broadcast units. Similarly, a broadcast device can be interpreted as a substrate molecule that can be catalysed by another broadcast device. As a result, a broadcast unit may produce an output broadcast device which results from some modifications of the input broadcast device (i.e., signal processing). 

\begin{table}[htbp]

  \centering	
	\begin{tabular}{|p{6cm}||p{6cm}|}\hline
	Biology & Broadcast language \\ \hline
	 sequence of amino acids from $\{A,R,N,D,C,E,\ldots\}$			
																	&  string of symbols from $\Lambda=\{0,\ 1,\ *,\ :,\ \lozenge, \triangledown,\ ,\ \triangle,\ '\}$\\ 	
	substrate molecule							&  input broadcast device\\ 
	product molecule 								&  output broadcast device\\ 
	molecule with no enzymatic function 
																	&  null broadcast device\\ 
	enzyme's active site 						&  broadcast unit \\ 
	enzyme molecule								&  broadcast device \\ 
	cellular milieu 								&  list of strings from $\Lambda$\\ \hline
	\end{tabular}
	\caption{Comparison of biological and broadcast language terminology}
	\label{tab:ComparisonOfBiologicalAndbroadcastsystemTerminology}
		
\end{table}

As a summary, Table \ref{tab:ComparisonOfBiologicalAndbroadcastsystemTerminology} presents a comparison between the biological and the broadcast system terminology. A detailed description of the broadcast language's syntax and semantics follows. 

\subsection{The syntax}
Our specification of the broadcast language partially adheres to the original proposal presented by Holland. As mentioned earlier, a number of features have been removed to facilitate the evaluation of this system. Moreover additional details have been introduced to complement Holland's proposal and resolve some identified ambiguous issues. We now describe the different structures constituting the broadcast language: the symbols, broadcast units and broadcast devices. The interpretation of the symbols, broadcast units and broadcast devices will follow. 

The broadcast language alphabet $\Lambda$ is finite and contains eight \textit{symbols}. The symbols constitute the atomic elements of the language. 
\[
	\Lambda=\{0,\ 1,\ *,\ :,\ \lozenge,\ \triangledown,\ \triangle,\ '\}
\]

Let $s_i$ be an arbitrary string (i.e., a molecular species) from $S$. A symbol occurring in $s_i$ is said to be quoted if it is preceded by the symbol $'$. $A\subseteq S$ is the set of strings over $\Lambda$ which do not contain unquoted occurrences of symbol $:$ and $*$. The set $A$ does not contain null strings. $S^*\subseteq S$ is the set of strings over $\Lambda$ which are of the form $*a_1:a_2$, where $a_1 \in A \wedge a_2 \in A$. The broadcast device's active sites are called \textit{broadcast units} which are arbitrary strings from $S^*=\{u_1,\ldots,u_l,\ldots,u_o\}$, $o$ is finite. The minimal length to realise a broadcast unit is $BD_{Lmin}=4$ where $length(*a_1:a_2)=BD_{Lmin}\wedge length(a_1)=length(a_2)=1$. Several broadcast units may be concatenated within a single broadcast device. $BD_{Lmax}$ is the fixed maximum string length of broadcast devices. A broadcast device $m_k$ may contain $0\leq n_u\leq \frac{BD_{Lmax}}{BD_{Lmin}}$ broadcast units. 

If $n_u=0$ then $m_k$ does not contain any broadcast units and $m_k$ is then called a \textit{null} broadcast device. A null broadcast device may \textit{only} be interpreted as an input broadcast device and is not capable of any enzymatic/computational functions. A broadcast device which is not null is said to be \textit{active} and may generate an output broadcast device (resulting from the computational function specified in the broadcast unit's action statement) upon the binding of an appropriate input broadcast device.

Some example broadcast devices are shown in Figure \ref{exBDevices}. We may note that $m_3$ is a null broadcast device. 

\begin{figure}
\begin{eqnarray*}
  m_1 	& = &	10*11'*\triangle0:1\triangle*:11\triangledown:11\triangledown\\
  m_2		& = &	011'**\triangledown:\lozenge1011\triangle\\
  m_3		& = &	11'*\triangle0:1\triangle'*:11\triangle:0001\lozenge
\end{eqnarray*}
\caption{Example broadcast devices}
\label{exBDevices}
\end{figure}

A broadcast device $m_k$ is parsed into broadcast units as follows:
\begin{itemize}
	\item Any prefix symbols occurring to the left of the leftmost unquoted $*$ are ignored (junk string).
	\item The first broadcast unit is designated from the leftmost unquoted $*$ to (not including) the next unquoted $*$ on the right \textit{if any}.
	\item Following broadcast units are obtained by repeating the above procedure for each successive unquoted $*$ from the left.
\end{itemize}
For example the broadcast device $m_1$:
\[
  m_1=10\underline{*11'*\triangle0:1\triangle}*\triangle00\underline{*11\triangledown:11\triangle}:1
\]
designates two distinct broadcast units $u_1$ and $u_2$:
\begin{eqnarray*}
  u_1&=&\ *11'*\triangle0:1\triangle\\
 	u_2&=&\ *11\triangledown:11\triangle
\end{eqnarray*}

\subsection{The semantics}
We describe the interpretation of the broadcast units and symbols.
\subsubsection*{Broadcast Units}
Let us consider the broadcast unit $u_l=\ *11'*\triangle0:1\triangle$. The string $u_{l_{IN}}=*11'*\triangle0$ stands for the broadcast's unit conditional statement (binding region) and may be translated into a pattern matching expression. Whereas the string $u_{l_{OUT}}=1\triangle$ refers to the broadcast unit's action statement and encodes for the computational function of $u_l$. 

When a broadcast unit's action expression is interpreted for producing an output broadcast device, a quote is removed from each quoted symbol. This quote mechanism allows one to prevent symbols from interpretation and to be passed into the output broadcast device (see next section for an example). 

In some cases, despite a broadcast unit $u_l$ being \textit{syntactically correct}, its action statement may not be executed. This inability to generate a product broadcast device (leading to an elastic reaction) may result from the nature of symbols present in the action expression. These cases are described in detail in the following section.

 
\subsubsection*{The symbols}
The interpretation of each symbol in $\Lambda = \{0,\ 1,\ *,\ :,\ \lozenge,\ \triangledown,\ \triangle,\ '\}$ is now presented. Within active broadcast devices, we may identify \textit{ignored} symbols. These symbols do not hold any functions in the binding and enzymatic operations of a given broadcast device. These substrings are analogous to non-coding DNA strings (junk strings). We illustrate the usage of each symbol through the depiction of example reactions:

\begin{itemize}

\item The quote symbol $'$ is used to ``quote'' a symbol in the arguments of a broadcast unit. The specific function of a quoted symbol is ignored when interpreted, regardless of the exact position of the quoted symbol in $u_{l_{IN}}$ or $u_{l_{OUT}}$. Nevertheless quoting 1s or 0s does not affect the function of these particular symbols.

For example:
\begin{eqnarray*}
r_{1}&=&\ *11'\triangle0:1'1\ +\ 11\triangle0 \rightarrow 11\\
r_{2}&=&\ *11'\triangle0:11\ +\ 1100 \rightarrow \emptyset
\end{eqnarray*}
whereas
\[r_{3}=\ *11\triangle0:1'\triangle\ +\ 1100 \rightarrow 1\triangle\]

In the above examples, quoting the symbol $\triangle$ prevents the interpretation of its specific function (described below) when occurring in either $u_{l_{IN}}$ or $u_{l_{OUT}}$. 

\item The star symbol * is the broadcast unit separator. This symbol, when unquoted, indicates that the following symbols until the next unquoted $*$ (if any) \textit{may} be interpreted as a broadcast unit. If a broadcast device species $s_i$ does not contain any unquoted $*$ then $s_i$ is a null broadcast device.
	
	\item The colon symbol $:$ is used as a punctuation mark to separate the parts (condition and action expressions) of a broadcast unit. Similarly to *, the colon is a structural symbol which is necessary to constitute a broadcast unit. If a string of symbols following an unquoted * does not contain any unquoted occurrences of :, then this string cannot be interpreted as a broadcast unit. If more than one unquoted $:$ is found in a broadcast unit then the second $:$ and anything to the right of it are ignored. 
	
A broadcast unit is identified by the pattern $*u_{l_{IN}}:u_{l_{OUT}}$ where $u_{l_{IN}}$ and $u_{l_{OUT}}$ are arbitrary strings from $A$. If $u_{l_{IN}}\notin A \vee u_{l_{OUT}}\notin A$ then the string $*u_{l_{IN}}:u_{l_{OUT}}$ is not a broadcast unit. $u_{l_{IN}}$ refers to the conditional statement of $u_l$ or pattern matching expression whereas $u_{l_{OUT}}$ is the computational or enzymatic function of $u_l$. $u_{l_{IN}}$ and $u_{l_{OUT}}$ are also called the ``arguments'' of $u_l$.


For example:
\begin{eqnarray*}
r_4&=&\ *10111:00\ +\ 10111 \rightarrow 00\\
r_5&=&\ 10111:00\ +\ 10110 \rightarrow \emptyset\\
r_6&=&\ *1011100\ +\ 10110 \rightarrow \emptyset\\
r_7&=&\ *:1011100\ +\ 10110 \rightarrow \emptyset
\end{eqnarray*}
In $r_4$, the species $*10111:00$ conforms to the pattern $*u_{l_{IN}}:u_{l_{OUT}}$ and is therefore an active broadcast device which contains a single broadcast unit. The condition statement $u_{l_{IN}}=10111$ matches the substrate species $10111$. As a result, the action statement $u_{l_{OUT}}=00$ generates the product species $00$. In $r_5$, $r_6$ and $r_7$, the enzyme species do not conform to the pattern $*u_{l_{IN}}:u_{l_{OUT}}$. These species are thus null broadcast devices resulting in $r_5$, $r_6$ and $r_7$ being elastic reactions.

	\item The symbols $0$ and $1$ possess different functions when located in either the condition or action statements of a broadcast unit. When 1 (or 0) occurs in $u_{l_{IN}}$ at the position $pos$, a substrate species $s_k$ would bind to $u_{l_{IN}}$ if $s_k$ presents a 1 (or 0) at the relative position $pos$. If 1 or 0 occurs in the action statement, a 1 or 0 is generated in the product species string accordingly.
		
A string such as $010110$ can be regarded as the \textit{tag} of a particular broadcast device. This tag can be employed by a broadcast unit to react with specific broadcast devices. 
	
For example: 
\begin{eqnarray*}
r_8&=&\ *10111:100\ +\ 10111 \rightarrow 100\\
r_9&=&\ *10111:100\ +\ 10110 \rightarrow \emptyset
\end{eqnarray*}
	

	\item Ordinarily the lozenge symbol $\lozenge$ acts as a single character wildcard. When this symbol is met in the conditional statement of a broadcast unit, it indicates that an input broadcast device ``colliding'' with the broadcast unit may present any single symbol at this position. This symbol occurring in the input broadcast device does not affect its acceptance or rejection by the broadcast unit. In no circumstances, $\lozenge$ may match a \textit{null} substring.
	
For example:
\begin{eqnarray*}
r_{10} & = &\ *10\lozenge11:00\ +\ 10011 \rightarrow  00\\
r_{11}& = &\ *10\lozenge11:00\ +\ 10:11 \rightarrow  00\\
r_{12}& = &\ *10\lozenge11:00\ +\ 11:11 \rightarrow  \emptyset\\
r_{13}& = &\ *10\lozenge:00\ +\ 10 \rightarrow  \emptyset
\end{eqnarray*}
In $r_{10}$, the enzyme species $s_1=*10\lozenge11:00$ would successfully react with any input broadcast devices of the form $10\lozenge11$ where $\lozenge$ indicates a single arbitrary symbol from $\Lambda$. 
	
However, $\lozenge$ may in some cases act as a multiple character wildcard. If $\lozenge$ occurs at the rightmost position of $u_{l_{IN}}$, then it indicates that an input broadcast device reacting with $u_l$ may present any suffix (i.e., any string of symbols from $\Lambda$) without affecting its acceptance or rejection by $u_l$. 

For example:
\begin{eqnarray*}
r_{14}&=& *1011\lozenge:100\ +\ 1011\underline{000} \rightarrow 100\\
r_{15}&=& *1011\lozenge:100\ +\ 1011\underline{010101010} \rightarrow 100
\end{eqnarray*}
Underlined strings designate the input broadcast device's substring that is matched by the multiple/single character wildcard. If an unquoted occurrence of $\lozenge$ occurs in $u_{l_{OUT}}$ then this symbol is ignored when $u_{l_{OUT}}$ is executed.

\item The reversed triangle symbol $\triangledown$ is a multiple character wildcard which may also act as a \textit{variable holder}. If this symbol occurs at the leftmost or rightmost position of $u_{l_{IN}}$, then an input broadcast device may present any arbitrary initial (prefix) or terminal (suffix) string of symbols and will successfully bind to  $u_{l_{IN}}$. 

If $\triangledown$ occurs in both $u_{l_{IN}}$ and $u_{l_{OUT}}$ then $\triangledown$ holds for \textit{value} the string of matched prefix or suffix substring. When the computational function $u_{l_{OUT}}$ is interpreted for execution, any occurrence of $\triangledown$ is replaced with its value. This allows one to pass a string of symbols from the input broadcast device to the output broadcast device (i.e., signal processing). 
	
For example:
\[r_{16}=\ *10\triangledown:\triangledown\ +\ 10\underline{011}\ \rightarrow 011\]
with $\triangledown=011$ whereas
\[r_{17}=\ *10\triangledown:\triangledown\triangledown\ +\ 10\underline{0100101}\ \rightarrow 01001010100101\] 	
with $\triangledown=0100101$.
\[r_{18}=\ *10\triangledown:\triangledown\triangledown\ +\ 110100101\ \rightarrow \emptyset\] 
	
If $\triangledown$ does not occur at the first or last position of  $u_{l_{IN}}$ then $\triangledown$ is ignored. If two $\triangledown$ symbols simultaneously occur at the first \textit{and} last position of $u_{l_{IN}}$ then the rightmost occurrence is ignored.
	
	\item The triangle symbol $\triangle$ is employed in the same manner as $\triangledown$ but designates a \textit{single} arbitrary symbol whose position can be anywhere in both arguments of a given broadcast unit.
For example:
\[r_{19}=\ *11\triangle0:1\triangle\ +\ 11\underline{0}0 \rightarrow 10\]
with $\triangle=0$ whereas 
\[r_{20}=\ *11\triangle0:1\triangle\ +\ 11\underline{1}0 \rightarrow 11\]
with $\triangle=1$.

Moreover, if a broadcast unit contains more than one (unquoted) $\triangle$ symbol then only the leftmost occurrence of $\triangle$ is operative and is to be interpreted by the broadcast unit. The other occurrences of $\triangle$ found in $u_{l{IN}}$ are ignored. A $\triangle$ symbol may occur anywhere within $u_{l{IN}}$. 

If $u_{l{OUT}}$ contains an unquoted occurrence of $\triangle$ or $\triangledown$ which is not present in $u_{l{IN}}$, then this symbol cannot be interpreted and is ignored.
\end{itemize}
Table \ref{tab:blexample} presents a number of example reactions that can be realised with the \MCS.
\begin{table}[ht]
	\centering
	
	\begin{tabular}{|l|l|l||l|}\hline
	\normalsize Enzyme & \normalsize Substrate & \normalsize Product & \normalsize Reaction\\ \hline
	$*\triangledown1:\ \triangledown0$  & $1:0$ & $\emptyset$ & elastic reaction\\
	$*\triangledown1:\ '*\triangledown$  & $0:1$ & $*0:1$ & activation\\
	$*\ '*0\triangledown:0\triangledown$  & $*0:1$ & $0:1$ & inhibition\\
	$*\triangledown:\triangledown$ & $*00:11$ & $*00:11$ & replication\\
	$*\triangledown0:\triangledown0$ & $*\triangledown0:\triangledown0$ & $*\triangledown0:\triangledown0$ & self-replication\\
	$*\triangledown1:\triangledown10$ & $*0:1$ & $*0:10$ & concatenation\\
	$*\triangledown1:\triangledown$ & $*0:1$ & $*0:$ & cleavage\\ 	
	\hline
	\end{tabular}
	
	\caption{Example reactions realised with the \MCS}
	\label{tab:blexample}
\end{table}

Finally, to clarify the relationship between the \MCS, MCS, LCS, broadcast language and Alchemy, an overview is provided and depicted in Fig.~\ref{fig:mcsbllcs}. 

\begin{figure}[ht]
	\centering
		\includegraphics[scale=0.4]{chapter4/mcsbllcs.eps}
	\caption{Overview of the \MCS~ and related systems. Alchemy and the Learning Classifier System (LCS) are inspirational methods to the \MCS, whereas the latter is based on the Molecular Classifier System (MCS) and Holland's broadcast language}.
	\label{fig:mcsbllcs}
\end{figure}

\section{Summary}
We enumerated our motivations to devise and employ the \MCS. The latter is an agent-based Artificial Chemistry which is derived from both the class of Molecular Classifier Systems and the Holland broadcast language. The MCS class was introduced and its generic system features (i.e., the MCS reactor model and mutational operators) were described. Our simplification of the Holland broadcast language was finally presented and illustrated with a range of example reactions. In the following chapter we explore the emergence and self-maintenance of closed-reaction networks in the \MCS~formalism.