Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-09T06:04:27.775Z Has data issue: false hasContentIssue false
  • English
  • Français

The automata theory of semigroup embeddings

Published online by Cambridge University Press:  09 April 2009

Michael Arbib
Michael Arbib
Affiliation:
Electrical Engineering Department Stanford UniversityStanford, California 94305, U.S.A.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The theorem of Trevor Evans [1] that every countable semigroup can be embedded in a two-generator semigroup becomes obvious in automata theory as the statement that every countable automaton can be embedded in one with binary inputs. Standard techniques of automata theory [1], [3] yield a proof of the Evans Theorem using wreath products, as in Neumann [4].

Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 8 , Issue 3 , August 1968 , pp. 568 - 570
Copyright
Copyright © Australian Mathematical Society 1968

References

[1]Arbib, M. A., ‘Automaton Decompositions and Semigroup Extensions’, in: The Algebraic Theory of Machines, Languages and Semi groups, Arbib, M. A. (Editor), Academic Press, (1968), 37–54.Google Scholar
[2]Evans, T., ‘Embedding Theorems for Multiplicative Systems and Projective Geometries’, Proc. Amer. Math. Soc. 3 (1952), 614–620.CrossRefGoogle Scholar
[3]Krohn, K. and Rhodes, J. L., ‘Algebraic Theory of Machines, I: The Decomposition Results’, Trans. Amer. Math. Soc. 116 (1965), 450–464.CrossRefGoogle Scholar
[4]Neumann, B. H., ‘Embedding Theorems for Semigroups’, J. London Math. Soc. 35 (1960), 184–192.CrossRefGoogle Scholar