\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{graphicx}
\usepackage{amsmath}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Sun Sep 30 01:05:01 2001}
%TCIDATA{LastRevised=Sun Sep 30 01:53:56 2001}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\input{tcilatex}
\begin{document}
\author{Y. Velinov \\
%EndAName
School of Mathematics Statistics and Information Technology\\
University of Natal, Pietermaritzburg, South Africa.}
\title{Multicategories in Computer Science}
\date{}
\maketitle
The concept of a multicategory first appeared in a paper of Lambek in 1979.
It was further generalized and studied by Szabo, and Velinov. Lambek was
inspired to introduce multicategories by certain analogy between the
Gentzen's sequent calculus and Bourbaki's treatment of bilinear maps, but
logic is not the only possible suggestive source. In essence any rich enough
mathematical area, which involves functions of many variables gives
intuitive support for introducing multicategories. Multicategories may
appear in several different\ forms. For example, considered as an algebraic
system, a $\mathsf{Y-}$multicategory can be defined as follows:
\emph{A \ }$Y-$\textbf{multicategory}\emph{\ }$Y$\emph{\ is a tuple }
\begin{equation*}
\mathcal{Y=}\langle \mathbf{O},\mathbf{A},+,\bullet ,dom,cod,\gamma
,I\rangle
\end{equation*}
\emph{such that }$Gr(Y)=$\emph{\ }$\langle O,A,+,\bullet ,dom,cod\rangle $%
\emph{\ is a mongraph ( a graph with additional monoidal operation }$+$\emph{%
\ on the objects and an unit }$\bullet $\emph{\ ), }$I:O\rightarrow A$\emph{%
\ is a unary operation\ selecting the identity arrow for each object and\ }$%
\gamma :A\times Con(Gr(Y))\times A\rightarrow A$\emph{\ is a partial
function (the arrow operation) which, when defined, puts in correspondence
an arrow denoted as\ }$x\lceil \perp \rceil y$\emph{\ to each tuple\ }$%
\langle x,\perp ,y\rangle $\emph{. The components of a }$Y-$\emph{%
multicategory fulfil the following axioms.}
\emph{For any arrows\ }$x,y,z,$\emph{\ and objects\ }$A,B,C,D,E$\emph{\ :}
\begin{itemize}
\item $x\lceil A\underline{B}C\rceil y$\emph{\ exists iff\ }$dom(x)=ABC$%
\emph{\ and\ }$cod(y)=B$\emph{;}
\item \emph{if\ }$x\lceil A\underline{B}C\rceil y$\emph{\ exists then\ }$%
cod(x\lceil A\underline{B}C\rceil y)=cod(x)$\emph{, and }$dom(x\lceil A%
\underline{B}C\rceil y)=Adom(y)B$\emph{;}
\item $(x\lceil A\underline{B}CDE\rceil y)\lceil Adom(y)C\underline{D}%
E\rceil z=(x\lceil ABC\underline{D}E\rceil z)\lceil A\underline{B}%
Cdom(z)E\rceil y$\emph{\ provided the described composites exist
(commutativity);}
\item $\left( x\lceil A\underline{B}C\rceil y\right) \lceil AD\underline{%
cod(z)}EC\rceil z=x\lceil A\underline{B}C\rceil \left( y\lceil D\underline{%
cod(z)}E\rceil z\right) $\emph{\ provided the described composites exist
(associativity);}
\item $I_{cod(x)}\lceil \underline{cod(x)}\rceil x=x\lceil \underline{dom(x)%
}\rceil I_{dom(x)}=x$\emph{.}
\end{itemize}
Multicategories can be applied in many areas of Computer Science. For
example, \ they can be used to describe and study finite automata, syntax
and semantics of formal grammars, derivation systems, term rewriting systems.
In my talk I will consider the main properties of multicategories and their
application to context-free derivation systems, and to the semantics of
generalized flow diagrams.
\end{document}