automatic groupAutomaticGroup2004-03-29 09:23:222004-08-03 11:22:21Definitionautomatic semigroupautomatic structure% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands hereLet $G$ be a finitely generated group. Let $A$ be a finite generating set for $G$ \PMlinkescapetext{closed} under inverses.
$G$ is an \emph{automatic group} if there is a language $L\subseteq A^*$ and a surjective map $f:L\rightarrow G$ such that
\begin{itemize}
\item $L$ can be checked by a \PMlinkname{finite automaton}{DeterministicFiniteAutomaton}
\item The language of all convolutions of $x,y$ where $f(x)=f(y)$ can be checked by a \PMlinkescapetext{finite automaton}
\item For each $a\in A$, the language of all convolutions of $x,y$ where $f(x).a=f(y)$ can be checked by a \PMlinkescapetext{finite automaton}
\end{itemize}
$(A, L)$ is said to be an \emph{automatic structure} for $G$.
Note that by taking a finitely generated semigroup $S$, and some finite generating set $A$, these conditions define an \emph{automatic semigroup}.