Thumbnail
Access Restriction
Subscribed

Author Pickett, H. E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1967
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract If an automaton is strongly connected, all of its automorphisms are regular permutations. It is proved that given any two groups $\textit{G}$ and $\textit{H}$ of regular permutations on finite sets $\textit{A}$ and $\textit{B},$ respectively, there exists strongly connected automata @@@@ and @@@@ such that $\textit{G}$ and $\textit{H}$ are the automorphisms groups of @@@@ and @@@@, @@@@ × @@@@ is strongly connected and the automorphism group of @@@@ × @@@@ is $\textit{G}$ × $\textit{H}.$ Also it is proved that the reduced semigroup of an automaton is a regular group of permutations iff the automorphism group of @@@@ is regular and @@@@ is strongly connected. Using this result we construct examples where the automorphism groups have the above property for $\textit{all}$ strongly connected automata on $\textit{A}$ and $\textit{B},$ and other examples where the automorphism group of @@@@ × @@@@ properly contains $\textit{G}$ × $\textit{H}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1967-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 14
Issue Number 2
Page Count 7
Starting Page 382
Ending Page 388


Open content in new tab

   Open content in new tab
Source: ACM Digital Library