CoChat

Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines

Open access
Krohn, Kenneth, Rhodes, John · 1965 · Transactions of the American Mathematical Society

The 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

Crossref · 10.1090/s0002-9947-1965-0188316-1

Cites

7 of 7 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

Citations

Cites

Show all 7 references

Research works printed but not linked: 1

  1. Hall, Marshall, Jr., 1959, The theory of groups

Cited by

See all 337

Metadata

Authors
Krohn, K., & Rhodes, J.
Venue
Transactions of the American Mathematical Society
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
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.