Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines
Open accessThe DOI matches its Crossref record; 7 of the 11 references it cites were found in a registry or an index.
Abstract
Introduction.In the following all semigroups are of finite order.One semigroup Si is said to divide another semigroup S2, written Si|S2, if Si is a homomorphic image of a subsemigroup of S2.The semidirect product of S2 by Si, with connecting homomorphism Y, is written S2 Xy Si.See Definition 1.6.A semigroup S is called irreducible if for all finite semigroups S2 and Si and all connecting homomorphisms Y, S\(S2Xy Si) implies S|S2 or S|Si.It is shown that S is irreducible if and only if either:(i) S is a nontrivial simple group, in which case S is called a prime; or (ii) S is one of the four divisors of a certain three element semigroup U3 (see Definition 2.1) in which case S is called a unit.We remark that an anti-isomorphism of a unit need not be a unit.Thus the theory is not symmetric.The explanation is that semidirect product can be written from the left or from the right.Let be a collection of finite semigroups.We define K(Sf) as the closure of Sunder the operations of division and semidirect product.See Definition 3.2.Then it is proved that SG K{Sf U {U3\) if and only if PRIMES (S) C PRIMES (SS).Here PRIMES (S) = {P\ P is a nontrivial simple group and P divides S\ and PRIMES (SS) =(J {PRIMES (S)\S G Sf ).In particular, Se#(PRIMES (S) U {U3\).A counterexample to the conjecture that SG 7/f(IRR(S)) justifies the distinction between primes and units as well as the inclusion of U3 in the above formulas.A novel feature of this paper is the use of functions on free semigroups, i.e. machines, to prove facts about finite semigroups.These above results are obtained as an immediate corollary of a more general theorem (proved here) which finds application as the basis for a prime decomposition theorem for finite state sequential machines.Further, by applying this theorem together with the powerful solvability criteria of Feit and Thompson and of Burnside, we find that Corollary 4.1 answers in important cases the question "What machines can be constructed by series-parallel from counters, delays and units?"See §4.A heuristic discussion of this paper occurs in [6].
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“On the other hand, the behavior (input–output function) of any (discrete) recurrent system can also be implemented by a system with a feed-forward architecture [54].”
From Integrated information theory (IIT) 4.0: Formulating the properties of phenomenal existence in physical terms (2023) · cites this paper as [54]
Citations
Cites
The algebraic theory of semigroups
Clifford, A. H., & Preston, G. B. (1964) · CERN Document Server (European Organization for Nuclear Research) · Cited by 3,638
Finite Automata and Their Decision Problems
Rabin, M. O., & Scott, D. (1959) · IBM Journal of Research and Development · doi:10.1147/rd.32.0114 · Cited by 1,879
THE ABSTRACT THEORY OF AUTOMATA
Glushkov, V. M. (1961) · Russian Mathematical Surveys · doi:10.1070/rm1961v016n05abeh004112 · Cited by 482 · cited 1×
“Then [H(f)]«—>[t]/ is a well-defined homomorphism of S'g (2) See references [3], [4], [6], and [7], and §4 of this paper for a discussion of machines and automata.”
BackgroundSOLVABILITY OF GROUPS OF ODD ORDER
Feit, W., & Thompson, J. G. (2012) · Cited by 385
Rees, D. (1940) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100017436 · Cited by 231
An Introduction to Mathematical Machine Theory
Elgot, C. C., & Ginsburg, S. (1965) · Mathematics of Computation · doi:10.2307/2004142 · Cited by 120
An introduction to mathematical machine theory
(1963) · Journal of the Franklin Institute · doi:10.1016/0016-0032(63)90871-8 · Cited by 101
Research works printed but not linked: 1
- Hall, Marshall, Jr., 1959, The theory of groups
Cited by
Albantakis, L., Barbosa, L., Findlay, G., Grasso, M., Haun, A. M., Marshall, W., Mayner, W. G. P., Zaeemzadeh, A., Boly, M., Juel, B. E., et al. (2023) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1011465 · Cited by 292
“On the other hand, the behavior (input–output function) of any (discrete) recurrent system can also be implemented by a system with a feed-forward architecture [65].”
Categories as algebra: An essential ingredient in the theory of monoids
Tilson, B. (1987) · Journal of Pure and Applied Algebra · doi:10.1016/0022-4049(87)90108-3 · Cited by 278
Cohen, R. S., & Brzozowski, J. A. (1971) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(71)80003-x · Cited by 158
A survey of some recent results in linear multivariable feedback theory
MacFarlane, A. G. J. (1972) · Automatica · doi:10.1016/0005-1098(72)90105-7 · Cited by 123
The kernel of monoid morphisms
Rhodes, J., & Tilson, B. R. (1989) · Journal of Pure and Applied Algebra · doi:10.1016/0022-4049(89)90137-0 · Cited by 81
Self-citation
Metadata
- Authors
- Krohn, K., & Rhodes, J.
- Venue
- Transactions of the American Mathematical Society
- Publisher
- American Mathematical Society (AMS)
- Published
- 1965
- Volume
- 116
- Issue
- 0
- Pages
- 450-464
- ISSN
- 0002-9947 (ISSN-L)
- 1088-6850
- OpenAlex
- W1979971526
- Cited by
- 327
- References
- 11
- Citations by year
- 2026: 3 · 2025: 4 · 2024: 6 · 2023: 8 · 2022: 7 · 2021: 18 · 2020: 9 · 2019: 10 · 2018: 11 · 2017: 2 · 2016: 10 · 2015: 11 · 2014: 8 · 2013: 6 · 2012: 9
- FWCI
- 9.94
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Transactions of the American Mathematical Society (publishedVersion)
- Funders
- Office of Naval Research
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Finite Group Theory Research
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Algebra and Logic
- Keywords
- finite semigroups, irreducible semigroups, semidirect products, simple groups
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. https://app.cochat.ai/papers/10.1090/s0002-9947-1965-0188316-1
- The paper
- Krohn, K., & Rhodes, J. (1965). Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society. https://doi.org/10.1090/s0002-9947-1965-0188316-1
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.