Talk:PlanetPhysics/Category of Automata

Original TeX Content from PlanetPhysics Archive

%%% This file is part of PlanetPhysics snapshot of 2011-09-01
%%% Primary Title: category of automata
%%% Primary Category Code: 00.
%%% Filename: CategoryOfAutomata.tex
%%% Version: 33
%%% Owner: bci1
%%% Author(s): bci1
%%% PlanetPhysics is released under the GNU Free Documentation License.
%%% You should have received a file called fdl.txt along with this file.        
%%% If not, please write to gnu@gnu.org.
\documentclass[12pt]{article}
\pagestyle{empty}
\setlength{\paperwidth}{8.5in}
\setlength{\paperheight}{11in}

\setlength{\topmargin}{0.00in}
\setlength{\headsep}{0.00in}
\setlength{\headheight}{0.00in}
\setlength{\evensidemargin}{0.00in}
\setlength{\oddsidemargin}{0.00in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.00in}
\setlength{\voffset}{0.00in}
\setlength{\hoffset}{0.00in}
\setlength{\marginparwidth}{0.00in}
\setlength{\marginparsep}{0.00in}
\setlength{\parindent}{0.00in}
\setlength{\parskip}{0.15in}

\usepackage{html}

% this is the default PlanetMath preamble. as your knowledge
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% define commands here
\usepackage{amsmath, amssymb, amsfonts, amsthm, amscd, enumerate}
\usepackage{xypic, xspace}
\usepackage[mathscr]{eucal}
\usepackage[dvips]{graphicx}
\usepackage[curve]{xy}
\theoremstyle{plain}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[section]
\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem*{notation}{Notation}
\newtheorem*{claim}{Claim}
\renewcommand{\thefootnote}{\ensuremath{\fnsymbol{footnote}}}
\numberwithin{equation}{section}
\newcommand{\Ad}{{\rm Ad}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\Cl}{{\rm Cl}}
\newcommand{\Co}{{\rm Co}}
\newcommand{\DES}{{\rm DES}}
\newcommand{\Diff}{{\rm Diff}}
\newcommand{\Dom}{{\rm Dom}}
\newcommand{\Hol}{{\rm Hol}}
\newcommand{\Mon}{{\rm Mon}}
\newcommand{\Hom}{{\rm Hom}}
\newcommand{\Ker}{{\rm Ker}}
\newcommand{\Ind}{{\rm Ind}}
\newcommand{\IM}{{\rm Im}}
\newcommand{\Is}{{\rm Is}}
\newcommand{\ID}{{\rm id}}
\newcommand{\grpL}{{\rm GL}}
\newcommand{\Iso}{{\rm Iso}}
\newcommand{\rO}{{\rm O}}
\newcommand{\Sem}{{\rm Sem}}
\newcommand{\SL}{{\rm Sl}}
\newcommand{\St}{{\rm St}}
\newcommand{\Sym}{{\rm Sym}}
\newcommand{\Symb}{{\rm Symb}}
\newcommand{\SU}{{\rm SU}}
\newcommand{\Tor}{{\rm Tor}}
\newcommand{\U}{{\rm U}}
\newcommand{\A}{\mathcal A}
\newcommand{\Ce}{\mathcal C}
\newcommand{\E}{\mathcal E}
\newcommand{\F}{\mathcal F}
%\newcommand{\grp}{\mathcal G}
\renewcommand{\H}{\mathcal H}
\renewcommand{\cL}{\mathcal L}
\newcommand{\Q}{\mathcal Q}
\newcommand{\R}{\mathcal R}
\newcommand{\cS}{\mathcal S}
\newcommand{\cU}{\mathcal U}
\newcommand{\W}{\mathcal W}
\newcommand{\bA}{\mathbb{A}}
\newcommand{\bB}{\mathbb{B}}
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bD}{\mathbb{D}}
\newcommand{\bE}{\mathbb{E}}
\newcommand{\bF}{\mathbb{F}}
\newcommand{\bG}{\mathbb{G}}
\newcommand{\bK}{\mathbb{K}}
\newcommand{\bM}{\mathbb{M}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bO}{\mathbb{O}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\bV}{\mathbb{V}}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\bfE}{\mathbf{E}}
\newcommand{\bfX}{\mathbf{X}}
\newcommand{\bfY}{\mathbf{Y}}
\newcommand{\bfZ}{\mathbf{Z}}
\renewcommand{\O}{\Omega}
\renewcommand{\o}{\omega}
\newcommand{\vp}{\varphi}
\newcommand{\vep}{\varepsilon}
\newcommand{\diag}{{\rm diag}}
\newcommand{\grp}{\mathcal G}
\newcommand{\dgrp}{{\mathsf{D}}}
\newcommand{\desp}{{\mathsf{D}^{\rm{es}}}}
\newcommand{\hgr}{{\mathsf{H}}}
\newcommand{\mgr}{{\mathsf{M}}}
\newcommand{\ob}{{\rm Ob}}
\newcommand{\obg}{{\rm Ob(\mathsf{G)}}}
\newcommand{\obgp}{{\rm Ob(\mathsf{G}')}}
\newcommand{\obh}{{\rm Ob(\mathsf{H})}}
\newcommand{\Osmooth}{{\Omega^{\infty}(X,*)}}
\newcommand{\grphomotop}{{\rho_2^{\square}}}
\newcommand{\grpcalp}{{\mathsf{G}(\mathcal P)}}
\newcommand{\rf}{{R_{\mathcal F}}}
\newcommand{\grplob}{{\rm glob}}
\newcommand{\loc}{{\rm loc}}
\newcommand{\TOP}{{\rm TOP}}
\newcommand{\wti}{\widetilde}
\newcommand{\what}{\widehat}
\renewcommand{\a}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\de}{\delta}
\newcommand{\del}{\partial}
\newcommand{\ka}{\kappa}
\newcommand{\si}{\sigma}
\newcommand{\ta}{\tau}
\newcommand{\lra}{{\longrightarrow}}
\newcommand{\ra}{{\rightarrow}}
\newcommand{\rat}{{\rightarrowtail}}
\newcommand{\ovset}[1]{\overset {#1}{\ra}}
\newcommand{\ovsetl}[1]{\overset {#1}{\lra}}

\begin{document}

 \begin{definition}
A {\em \htmladdnormallink{classical automaton}{http://planetphysics.us/encyclopedia/StableAutomaton.html}} $\A$, (or simply {\em automaton}, or
{\em sequential machine}, is defined as a quintuple of sets, $I,O$ and $S$, and set-theoretical mappings,

$$(I, O, S, \delta: I \times S \rightarrow S; \lambda: S \times S \rightarrow O),$$

with $\delta$ being called the {\em \htmladdnormallink{transition function}{http://planetphysics.us/encyclopedia/StableAutomaton.html}} and $\lambda$ being called the {\em \htmladdnormallink{output function}{http://planetphysics.us/encyclopedia/StableAutomaton.html}}.
\end{definition}

\begin{definition} A {\em categorical automaton} $\A_C$ or {\em discrete and finite/countable, categorical \htmladdnormallink{dynamic system}{http://planetphysics.us/encyclopedia/GenericityInOpenSystems.html}} is defined by a \htmladdnormallink{commutative square diagram}{http://planetphysics.us/encyclopedia/Commutativity.html} containing all of the above components and assuming that $S_A$ is either a countable or finite set of discrete states:

$$\begin{xy}
*!C\xybox{
\xymatrix{
{I \times S }\ar[r]^{\delta}\ar[d]_{t}&{S}\ar[d]^{o}\\
{S \times S}\ar[r]_{\lambda}&{O}
} }\end{xy}$$

\end{definition}

With the above definition one can now define \htmladdnormallink{morphisms}{http://planetphysics.us/encyclopedia/TrivialGroupoid.html} between automata and their \htmladdnormallink{composition}{http://planetphysics.us/encyclopedia/Cod.html}. If the automata are defined by \htmladdnormallink{square diagrams}{http://planetphysics.us/encyclopedia/Commutativity.html} such as
the one shown above, and \htmladdnormallink{diagrams}{http://planetphysics.us/encyclopedia/TrivialGroupoid.html} are defined by their associated \htmladdnormallink{functors}{http://planetphysics.us/encyclopedia/TrivialGroupoid.html}, then automata homomorphisms are in fact defined as \htmladdnormallink{natural transformations}{http://planetphysics.us/encyclopedia/VariableCategory2.html}
between diagram functors. One also has a consistent, simpler definition
as follows.

\begin{definition} A \emph{\htmladdnormallink{homomorphism}{http://planetphysics.us/encyclopedia/TrivialGroupoid.html} of automata} is a morphism of automata quintuples that preserves \htmladdnormallink{commutativity}{http://planetphysics.us/encyclopedia/TrivialGroupoid.html} of the set-theoretical mapping compositions of both the transition function $\delta$ and the output function $\lambda$.
\end{definition}

With the above two definitions now we have sufficient data to define the category of automata and automaton homomorphisms.

\begin{definition}
The \emph{category of automata} is a category of automata quintuples
$(I_X, O_X, X, {\delta}_X: I_X \times X \rightarrow X; {\lambda}_X: X \times X \rightarrow O)$ and automata homomorphisms $h:{\A}_i \rightarrow {\A}_j$,
such that these homomorphisms \htmladdnormallink{commute}{http://planetphysics.us/encyclopedia/Commutator.html} with both the transition and the output functions of any automata ${\A}_i$ and ${\A}_j$.
\end{definition}

\textbf{Remarks:}
\begin{enumerate}
\item Automata homomorphisms can be considered also as automata {\em transformations} or as \htmladdnormallink{semigroup}{http://planetphysics.us/encyclopedia/TrivialGroupoid.html} homomorphisms, when the \htmladdnormallink{state space}{http://planetphysics.us/encyclopedia/StableAutomaton.html}, $X$, of the automaton is defined as a \emph{semigroup} $\mathcal{S}$.
\item Abstract automata have numerous realizations in the real world as : machines, \htmladdnormallink{robots}{http://planetphysics.us/encyclopedia/Program3.html}, devices, computers, \htmladdnormallink{supercomputers}{http://planetphysics.us/encyclopedia/SupercomputerArchitercture.html}, always considered as \emph{discrete} state space sequential machines.
\item Fuzzy or analog devices are not included as standard automata.
\item Similarly, \emph{variable (transition function)} automata are not included, but Universal Turing (UT) machines are.
\end{enumerate}

\begin{definition} An alternative definition of an automaton is also in use:
as a five-tuple $(S, \Sigma, \delta, I, F)$, where $\Sigma$ is a non-empty set of symbols
$\alpha$ such that one can define a {\em configuration} of the automaton as a couple
$(s,\alpha)$ of a state $s \in S $ and a symbol $\alpha \in \Sigma $. Then $\delta$
defines a ``next-state relation, or a transition relation'' which associates to each configuration
$(s, \alpha)$ a subset $\delta (s,\alpha)$ of S- the state space of the automaton.
With this formal automaton definition, the \emph{\htmladdnormallink{category}{http://planetphysics.us/encyclopedia/Cod.html} of abstract automata} can be defined by specifying automata homomorphisms in terms of the morphisms between five-tuples representing such abstract automata.
\end{definition}


\begin{example}
A special case of automaton is when all its transitions are {\em reversible}; then its state space is a \htmladdnormallink{groupoid}{http://planetphysics.us/encyclopedia/QuantumOperatorAlgebra5.html}. The {\em category of reversible automata} is then a \htmladdnormallink{2-category}{http://planetphysics.us/encyclopedia/2Category.html}, and also a subcategory of the 2-category of groupoids, or the \htmladdnormallink{groupoid category}{http://planetphysics.us/encyclopedia/GroupoidCategory3.html}.
\end{example}

\subsection{Remarks:}
Other definitions of automata, sequential machines, semigroup automata or cellular automata lead to subcategories of the category of automata defined above. On the other hand, the \htmladdnormallink{category of quantum automata}{http://planetphysics.us/encyclopedia/CategoryOfQuantumAutomata.html} is not a subcategory of the automata category defined here.

\end{document}