Monoid

Version

v4 · 2026-08-30 · History

Prime #

1402

Origin domain

Mathematics

Subdomain

abstract algebra → Mathematics

Related primes

Semigroup

Core Idea

A monoid is a triple (M, •, e): a carrier set M, one binary operation • that is total and closed on M, and one distinguished element e. Two laws govern the whole structure — associativity, (a • b) • c = a • (b • c), and two-sided neutrality, e • a = a • e = a. There is no third law: neither commutativity nor inverses is required. ^[1]

The neutral element is not a stipulation that could have gone otherwise. If e and e' are both two-sided identities for the same operation, then e = e • e' = e', so a monoid has exactly one identity; "the" identity is precise language, not a convenient abuse of it. ^[2]

The prime names one rung on a ladder. A magma commits only to closure; a semigroup adds associativity; a monoid adds the neutral element; a group adds an inverse for every element. Each axiom shrinks the population of instances and enlarges the theorems holding of every survivor, and monoid is the rung at which every finite sequence of carrier elements — the sequence of length zero included — acquires a single well-defined product. ^[3]

The two laws buy two separable payoffs. Associativity yields generalised associativity: a₁ • a₂ • ⋯ • aₙ has one value however it is bracketed, provided the left-to-right order of the factors is left alone. Neutrality yields the empty product: a fold over zero elements is not undefined, not an error, and not a special case, but e. Together they say a finite sequence may be cut anywhere — its ends included, into empty pieces — reduced within the pieces, and recombined, unchanged. Every downstream use, from string concatenation to sharded aggregation, cashes out that sentence.

Structural Signature

One carrier set + one closed associative operation + one unique two-sided neutral element → a parenthesization-independent product for every finite sequence, the empty sequence included.

The signature is always a set-plus-operation pair, never a set alone. The naturals form a monoid under addition with identity 0, a second monoid under multiplication with identity 1, and neither under subtraction, which is not closed on them and not associative anywhere. Naming a monoid therefore means naming three things. ^[1]

Recurring features:

• One carrier, one total operation. Exactly one binary operation, defined for every ordered pair of carrier elements — no partial cases, no side conditions, no second operation.
• Closure. Combining two carrier elements yields a carrier element, so composition iterates indefinitely without leaving the structure.
• Associativity. (a • b) • c = a • (b • c). The law constrains grouping only, and says nothing about the order in which factors appear.
• A two-sided identity, and exactly one. Some e satisfies e • a = a • e = a for every a, and the axioms force it to be unique rather than merely permitting a choice.
• A defined empty product. Reducing an empty sequence yields e, making an empty chunk, partition, or input an ordinary case rather than an exception.
• No inverse commitment. Nothing guarantees a b with a • b = e, so cancellation, division, undo, and retraction are unavailable at this tier.
• Structure-preserving maps carry two obligations. A monoid homomorphism must satisfy both f(a • b) = f(a) • f(b) and f(e) = e'; unlike the group case, the second does not follow from the first. ^[2]

That last feature is the one most often dropped, and it has a two-element witness. Map the one-element monoid into the multiplicative monoid on {0, 1} by sending its sole element to 0. The map respects multiplication, since 0 × 0 = 0, yet misses the identity 1. It is a semigroup homomorphism between monoids and not a monoid homomorphism — the gap that lets a merge function pass every pairwise test and still corrupt the empty case.

What It Is Not

Monoid does not claim that order is irrelevant. Associativity governs brackets, not sequence. Function composition, matrix multiplication, string concatenation, and migration chains are all monoids and none is commutative. Reasoning that "the merge is a monoid, so shards may be combined in whatever order they arrive" assumes commutativity, a separate axiom. The real entitlement is narrower: any grouping, provided the sequence is respected.

Monoid does not claim the identity is distinguished in any way besides neutrality. It is not a maximum, a minimum, an absorbing element, or a fixed point. An absorbing element swallows every input rather than preserving it, and one object can play both roles under different operations: the empty set is the identity for union and the absorber for intersection.

Monoid does not claim that having an identity is an achievement. Any semigroup becomes a monoid by adjoining one fresh element and declaring it neutral. What the algebra cannot supply is meaning: whether the adjoined element denotes anything real — an empty shipment, a window with no events — is a modelling question, and a unit that names nothing is a sentinel that eventually leaks into an interface. ^[2]

Monoid does not claim that a type signature suffices. A method shaped combine(a, a) -> a alongside a value called empty is not thereby a monoid; the laws must hold on the actual values. IEEE-754 floating-point addition has a plausible unit in +0.0 and is not associative, so parallel summation of the same floats returns different totals under different partitionings — a defect that hides because it is invisible at small scale and on one core. ^[4] Averaging fails harder, being non-associative under every bracketing. "Last write wins" merges are associative; "merge and warn on conflict" usually is not.

Monoid claims nothing about size, generation, or decidability. Monoids may be finite or infinite, free or finitely presented, and membership does not make expression equality checkable.

Broad Use

Formal languages and automata. Finite strings over an alphabet, under concatenation with the empty string, form the free monoid and the paradigm case. Functions on states induced by input words form an automaton's transition monoid; quotienting the free monoid by a language's Myhill–Nerode congruence gives its syntactic monoid. The classification results are sharp: a language is regular exactly when its syntactic monoid is finite, and star-free exactly when that monoid is aperiodic. ^[5]

Programming languages and libraries. Haskell's Semigroup and Monoid classes, Scala's Cats and Algebird, Rust folds seeded with a zero, and the Writer construction parameterised by an arbitrary monoid. The standard instances — sum, product, minimum, maximum, any, all, first, last, endomorphism composition — catalogue the same axioms over different carriers.

Parallel and distributed computation. MapReduce combiners, tree aggregation, parallel prefix scans, GPU reductions, sharded counters, and segment trees over an arbitrary monoid all rest on the same entitlements, and all require an explicit zero because the framework, not the programmer, decides how many partitions there are and whether any is empty. ^[6]

Streaming and approximate structures. Mergeable sketches — HyperLogLog, Bloom filters, count-min, t-digest — are engineered so that merge is associative with the empty sketch as unit, which is what lets partial results from separate machines combine without coordination.

Category theory and semantics. A monoid is exactly a category with one object: elements are the morphisms, the operation is composition, the identity element is the identity morphism. Generalising gives monoid objects in a monoidal category, and a monoid acting on a set is a deterministic state machine.

Infrastructure. Layered configuration merge with the empty override as unit, patch composition, middleware chains with a pass-through handler, and the join-semilattices underlying state-based CRDTs.

Clarity

The prime's clarifying work is to pull apart four questions that talk of "combining things" runs together: whether combining stays inside the set, whether bracketing changes the answer, whether there is a do-nothing value, and whether a combination can be undone. Those commitments are logically independent, and monoid names the tier at which the first three hold and the fourth does not. Naming it stops a practitioner importing a guarantee that was never bought. ^[3]

The confusion it dissolves most often is between associativity and commutativity, which coincide in the arithmetic everyone learns first. Once the question splits, the consequence is concrete: a non-commutative monoid parallelises by grouping but not by racing, so a merge that is correct in a balanced reduction tree can be wrong under out-of-order arrival.

It also separates a default from an identity. A default is any value someone chose to start the accumulator with; an identity is a value the operation cannot distinguish from absence. Seeding a sum with 1 changes every answer; seeding it with 0 cannot change any. The identity is thus the only seed that makes a result independent of how often the accumulator was initialised, which is why frameworks that re-initialise per partition need one.

Finally, it fixes the word "identity" itself: here it is always relative to a stated operation, never a property an object holds alone.

Manages Complexity

Once an operation is known to be a monoid, a class of bookkeeping becomes provably irrelevant and can be discarded rather than tolerated. You stop tracking parenthesization, how many workers took part, where the chunk boundaries fell, whether partitions were equal in size, whether the reduction tree was balanced, whether the final batch was short, and whether any partition came back empty. All of those describe the shape of the computation, and the axioms say the value is invariant under every one of them; what remains to be tracked is the ordered sequence of inputs. ^[6]

The identity carries a distinct share of that reduction. It deletes a family of special cases from code and proofs alike — no "if empty then raise", no separate base case, no sentinel, no optional wrapper around every accumulator — and it makes the interface uniform: a reducer with a unit has the same contract for a billion records, one record, or none, so a single implementation serves a batch job, a streaming window, and a unit test.

It also bounds the audit surface. Correctness under rescheduling is otherwise an end-to-end argument about a scheduler nobody controls; here it reduces to a law check on a two-argument function, dischargeable by property tests over triples.

Abstract Reasoning

The prime licenses a fixed procedure. Name the carrier precisely, including whether the empty or zero object belongs to it, since that decision alone separates semigroup from monoid in most real cases. Check closure. Then try to falsify associativity before trying to prove it — on a finite carrier a mechanical check over all triples, on an infinite one a hunt among edge elements, where non-associativity almost always surfaces first. Then look for a two-sided identity, checking both sides: a semigroup can carry many left identities and no right identity, so one side proves nothing. If none exists, decide deliberately between adjoining one and dropping a tier.

When the checks pass, conclusions follow with no further argument about the substrate. Any bracketing is legal. Any chunking is legal, empty chunks included. The structure embeds into the monoid of endofunctions on its own carrier by left translation, so function composition is the universal case; and a homomorphism out of a free monoid is fixed entirely by where the generators go, so defining a map on the alphabet defines it on every word. ^[2]

The discipline is completed by keeping the near-misses to hand, since classification turns on the failing axiom rather than on resemblance. Positive integers under addition are closed and associative with no neutral element, and become a monoid the moment zero joins the carrier. Reals under maximum need negative infinity adjoined. Subtraction fails one step earlier, at associativity. Averaging fails there too and cannot be rescued by adjoining anything, the defect lying in the operation rather than the carrier.

Knowledge Transfer

What travels is the axiom set and everything derivable from it alone, which is more than it looks: reassociation, the empty case, uniqueness of the identity, the two-part homomorphism condition, the free-monoid universal property, and the Cayley embedding all hold in any substrate with no further evidence required. This is why someone who has understood string concatenation has already understood distributed reduction, and why transfer is cheap in practice: to define an aggregation over a stream it is enough to say what one event contributes and what the empty stream contributes.

What does not travel is whatever quietly depends on a stronger axiom. Order-independence needs commutativity. Retry-safety under at-least-once delivery needs idempotence. Undo, retraction, window eviction, and incremental deletion need inverses, which is to say a group. They get carried along because the arithmetic that seeded the intuition had all of them, and the resulting defects are silent: a deletion implemented as subtraction on a structure without subtraction returns a plausible number rather than an error.

Two further limits deserve stating. Decidability does not transfer: the word problem for finitely presented monoids is undecidable, so knowing that a structure is a monoid does not mean two expressions in it can be compared. ^[7] Nor does the cost model, since associativity guarantees equal values under regrouping and never equal cost — left-nested list append is quadratic where right-nested is linear. Closing that gap is an engineering move, not a consequence of the axioms.

Examples

Formal/abstract

Deciding whether a long string of brackets is balanced looks inherently sequential: the textbook algorithm pushes and pops a stack left to right. The prime turns it into a parallel reduction. Let the carrier be ordered pairs of naturals, where (a, b) records that a fragment, once internally reduced, leaves a closers unmatched on its left and b openers unmatched on its right. Define (a, b) • (c, d) = (a + max(0, c − b), d + max(0, b − c)): the b dangling openers annihilate against the c demanded closers, and whichever side has a surplus keeps it. The identity is (0, 0). Send "(" to (0, 1) and ")" to (1, 0), and the free-monoid universal property extends those assignments to every string. A string is balanced exactly when its image is (0, 0).

The structure repays inspection. It is associative, because cancellation between adjacent fragments is order-preserving and the surplus leaving a bracketing does not depend on the grouping. It is emphatically not commutative: "()" maps to (0, 1) • (1, 0) = (0, 0) while ")(" maps to (1, 0) • (0, 1) = (1, 1). And it has no inverses: (0, 1) has a right partner in (1, 0) but no left one, and (1, 1) has neither. What has been built is the bicyclic monoid, the standard witness that a monoid can be infinite, can contain elements with a one-sided inverse and no two-sided one, and can still have nothing but the identity invertible. ^[8]

Mapped back: every clause of the signature does visible work here. The carrier was chosen as pairs rather than a counter precisely so the operation would close, which is why a naive depth counter fails on ")(" and this does not. Associativity licenses cutting the input at arbitrary offsets and reducing the pieces on separate cores. The identity makes an empty chunk an ordinary input rather than a branch. The absent inverse is why the algorithm reports residual imbalance but cannot repair it. And the universal property is why the definition took two lines.

Applied/industry

A telemetry pipeline computes per-region summaries over billions of events across a few thousand partitions, and each requested statistic is a fresh encounter with the axioms. Total bytes is immediate: naturals under addition with zero. Maximum latency is not, since maximum on observed values is associative and closed but unit-less: the carrier must gain a bottom element, or the accumulator be wrapped so "nothing yet" is the unit. Mean latency is not a monoid at all, averaging being non-associative; the repair changes the carrier from a number to a running sum-and-count pair under componentwise addition, identity (0, 0), dividing once at the end. Distinct users is a monoid under set union with a carrier too large to ship, so union is replaced by sketch merge, associative and commutative with the empty sketch as unit, trading exactness for a bounded carrier that still satisfies the laws. ^[9]

In operation it is the identity, not associativity, that earns its keep. Empty partitions are routine — a quiet shard, a late file, a backfill of an idle hour — and a semigroup would special-case each. The characteristic production failure is supplying a zero that is not actually neutral: the job does not crash, it returns totals that drift with the partition count, discovered when someone resizes the cluster. What the pipeline may not do is subtract; evicting the oldest minute from a windowed maximum needs an inverse the tier withholds, and the working substitute is to retain per-slice values and re-combine the survivors.

Mapped back: each engineering decision here is a signature decision in disguise. Closure forced the sketch, the honest carrier not fitting on a machine. Associativity makes the partition count invisible to the answer. The identity turns the empty partition from a branch into a value. The missing inverse turns eviction from a subtraction into a re-fold over retained slices. The discipline collapses to one instruction: choose a carrier on which the combining step is associative and has a unit, then stop reasoning about the schedule.

Structural Tensions

T1 — Identity as convention versus identity as structure. Adjoining a fresh neutral element to a semigroup is always possible and always cheap, so having an identity is never a deep obstruction to qualifying. Yet where one already exists it is forced and unique, not chosen. The tension lies between how easy the axiom is to satisfy formally and how hard honestly: an adjoined unit denoting nothing in the substrate obeys every law while smuggling a sentinel into the domain model, where it surfaces later as a null nobody expected.

T2 — When the empty fold is meaningful and when it is arbitrary. The sum of no numbers is zero, defensibly. The maximum of no numbers is negative infinity, a convention that must be represented somehow and usually leaks. The average of no observations has no identity at all. The tension is between the axioms, which demand a total answer for the empty case, and the domain, which sometimes refuses to supply one; forcing one anyway converts a modelling gap into a silent value that later reads as data.

T3 — Associativity does the parallel work; the identity removes the special cases. Reassociation alone buys tree reduction, so a semigroup already parallelises and the identity adds no throughput. What it adds is totality: every chunking becomes legal, degenerate ones included, so the code loses its branches and the proof its side conditions. The tension is that engineers credit the wrong axiom in both directions — dismissing the unit as ceremony, or believing it made the computation splittable — and each error misdirects the fix when a merge proves unsound.

T4 — The standing pull toward inverses. Everything that makes the concept feel natural — addition, concatenation, composition — sits near structures where undoing is available, so retraction gets assumed. Sliding windows, data corrections, unsubscribes, refunds, and cache invalidations all want subtraction, and the tier has none. The tension is that the illegal operation is usually implementable: one can subtract from a counter and get a number. The result is plausible, wrong on approximate or idempotent carriers, and raises no error to notice.

T5 — Regrouping is not reordering. Associativity licenses moving brackets and nothing else, but the arithmetic seeding most intuitions is commutative too, so the two entitlements fuse. The consequence is a common defect: a merge correct in a balanced reduction tree becomes wrong once results arrive out of order, and stays invisible in single-node tests. The tension is that non-commutative monoids — composition, concatenation, matrix product, patch application — are the ordinary case rather than the exotic one, and intuition points the other way.

T6 — Equal value, unequal cost, and the price of the minimal tier. The axioms are extensional: they promise the same answer under any grouping and say nothing about the work of obtaining it, so left-nested and right-nested folds agree on the result and differ asymptotically. Choosing the weakest sufficient tier likewise maximises instances while minimising the theorems available about each. The tension is that portability and leverage move in opposite directions, and declaring only "monoid" forgoes what commutativity, idempotence, or inverses would have given.

Structural–Framed Character

Monoid sits at the structural end of the structural–framed spectrum, graded structural with an aggregate of 0.00 and all five criteria at zero. The relation that travels is small and complete: a carrier set, one total internal binary operation closed on it, associativity, and a two-sided identity leaving every element unchanged. Inverses are not required — that is what places the prime between semigroup and group — and the identity gives empty products and empty folds their value.

The criterion doing the most work is import-vs-recognize, and it reads zero because the paradigm cases do not borrow algebra, they satisfy it. Strings under concatenation, endofunctions under composition, sets under union, database aggregates, and distributed folds preserve the axioms without importing a single subject-matter mechanism.

Vocabulary travels at zero: the three portable properties are closure, associativity, and a neutral element, and each substrate already states them in its own terms. Evaluative weight reads zero, the axioms being a specification rather than a recommendation — a magma or a semigroup is not worse, only differently equipped. Institutional origin reads zero, no convention or body being required to license an identity element, and human-practice-bound reads zero, since the axioms hold of the carrier and its operation whether or not anyone is folding anything.

The abstraction is natively mathematical yet travels as an executable interface, so the test for applying it is whether closure, associativity, and a two-sided identity hold. Where they do, folds and incremental aggregation come with them; where every element also has an inverse, what is instantiated is a group.

Substrate Independence

Monoid is about as substrate-independent as a prime can be — composite 5 / 5 on the substrate-independence scale. What travels is an entire structure rather than one distinguished member: a carrier, a total associative operation closed on it, and the unique neutral element that operation admits, together yielding a product for every finite sequence that survives any rebracketing and is defined even when the sequence is empty. Verifying two laws is the whole cost of entry, so strings under concatenation, endofunctions under composition, sets under union, paths joined end to end, database aggregates, and sharded distributed folds all qualify without any of them contributing subject-matter machinery of their own. The axioms are natively mathematical yet behave as an executable interface, which is why breadth and demonstrated instances keep pace with the abstraction.

• Composite substrate independence — 5 / 5
• Domain breadth — 5 / 5
• Structural abstraction — 5 / 5
• Transfer evidence — 4 / 5

Relationships to Other Abstractions

Current abstraction Monoid Prime

Parents (2) — more general patterns this builds on

• Monoid is a kind of Semigroup Prime

  Monoid is a strict specialization of Semigroup.

• Monoid is part of Identity Element Prime

  A two-sided Identity Element is a constitutive part of every Monoid.

Children (3) — more specific cases that build on this

• Exterior Algebra Domain-specific is a kind of Monoid

  The accepted reference-grade review places Exterior Algebra under Monoid because the child instantiates or depends on the parent's broader structure while retaining its own constitutive identity.

• Free monoid Domain-specific is a kind of Monoid

  The proposed strict upward parent is prime:monoid.

• Group Prime is a kind of Monoid

  A Group is exactly a Monoid in which every element additionally has an inverse.

Hierarchy paths (5) — routes to 5 parentless roots

• Monoid → Semigroup → Set and Membership

Show alternative paths (4)

Neighborhood in Abstraction Space

Monoid sits in a sparse region of abstraction space (64^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely rather than landing on a neighbor.

Family — Sets, Order & Foundational Structure (19 primes)

Nearest neighbors

• Identity Element — 0.75
• Semigroup — 0.73
• Associativity — 0.72
• Group — 0.70
• Category — 0.70

Computed from structural-signature embeddings · 2026-09-10

Not to Be Confused With

Monoid must first be distinguished from Semigroup, its immediate parent and the source of most misclassification. A semigroup commits to a carrier, closure, and associativity and stops. Every monoid is a semigroup with one element singled out; forget the identity and what remains satisfies every semigroup commitment. Without a neutral element there is no value for the empty product, so a fold over an empty sequence is undefined and every consumer handles absence separately; with one, absence is just another value. The boundary is concrete: nonempty strings under concatenation are a semigroup and become a monoid when the empty string is admitted. The engineering consequence is asymmetric — both tiers parallelise, since reassociation is what splits a computation, but only the monoid makes every chunking legal, which is why frameworks that partition on your behalf demand a zero and libraries that fold a sequence you supplied often do not.

Monoid must equally be distinguished from Group, its immediate child. A group is a monoid in which every element has a two-sided inverse, and that one axiom buys cancellation, solvable equations, and reversibility — precisely what a monoid withholds. Read practically: a monoid supports accumulation, a group supports accumulation plus retraction. A running total in a group can be decremented; a maximum, a set union, or a Bloom filter cannot be un-merged at all. Whenever a design needs to remove a contribution already folded in — evicting the oldest window slice, backing out a bad batch, unwinding a committed effect — it is asking for the group axiom, and must move to a group, retain contributions separately and re-fold, or accept approximation. The commonest failure is not noticing that the request was made.

Magma sits one rung below the semigroup and marks the other boundary. A magma has a carrier and a closed binary operation and no further law, so nothing is licensed: products depend on bracketing, folds are not splittable, and "the" product of a sequence has no meaning. Subtraction on the integers and averaging on the reals are magmas, which is exactly why neither parallelises. The distinction matters because a merge function is a magma until someone checks associativity, and that check is the whole content of the promotion.

Identity Element is a constituent of the prime rather than a rival, and mistaking the part for the whole is a different error from confusing tiers. An identity element is a role some element plays relative to some operation, and it occurs far outside this setting — identity morphisms, no-op transformations, the empty patch. The prime is the whole species: carrier, closed associative operation, and such an element together. An identity without associativity gives a unital magma, which licenses nothing about folds; associativity without an identity gives a semigroup. Only the pair yields the parenthesization-independent product over arbitrary finite sequences, so citing the identity alone never establishes membership.

Associativity and Closure, taken as bare properties, stand to the prime as the identity element does: portable commitments that travel into any substrate, where the prime bundles them with a specific carrier and the theorems that follow. Saying an operation is associative is a claim about the operation; saying a structure is a monoid is a claim about a set-and-operation pair, and it unlocks the free-monoid universal property, the Cayley embedding, and classification results that only make sense once the carrier is fixed.

Commutative Monoid and its idempotent specialisation, the join-semilattice, are strictly stronger and are frequently what a design actually needs. A commutative monoid permits reordering as well as regrouping, which makes unordered merge and out-of-order arrival safe; an idempotent one additionally permits double-counting, which makes at-least-once delivery safe and underwrites state-based CRDTs. Claiming "monoid" where the system depends on either understates the requirement, and the defects appear only under retries or reordering.

Finally, monoid is not Fold or Aggregation. A fold is an operation over a sequence and an aggregation a computation summarising a collection; either can use any binary function whatever. The monoid is the algebraic certificate that a particular fold is independent of its bracketing and defined on the empty case. Folds exist without monoids and give order-dependent, non-splittable answers; monoids exist without anyone folding anything.

Solution Archetypes

No catalogued solution archetypes reference this prime yet.

Notes

The prime's placement explains an asymmetry practitioners notice without naming. Almost every useful combining operation in software is at least a semigroup, many are monoids, a minority are commutative, and few are groups. The scarcity of inverses is not accidental: aggregation and lossy compression discard information, and what discards information cannot be inverted. Wanting undo is usually a request to stop discarding — a storage decision rather than an algebraic one.

References

[1] Lang, Serge. Algebra. Revised 3^rd ed., Graduate Texts in Mathematics 211. Springer, 2002. Defines a monoid as a set with an associative law of composition and a two-sided unit element, requiring neither commutativity nor inverses, and gives the additive and multiplicative monoids of the natural numbers. registry ↩a ↩b

[2] Howie, John M. Fundamentals of Semigroup Theory. London Mathematical Society Monographs, New Series 12. Clarendon Press, Oxford, 1995. Supplies the uniqueness of a two-sided identity, the adjunction of an identity to any semigroup, the monoid homomorphism conditions including preservation of the unit, and the Cayley embedding into the endofunction monoid by translation. registry ↩a ↩b ↩c ↩d

[3] Bourbaki, Nicolas. Algebra I: Chapters 1-3. Hermann and Addison-Wesley, 1974. Establishes the magma-semigroup-monoid-group hierarchy, the general associativity theorem, and the empty-product convention that gives every finite sequence, the empty one included, a well-defined product. registry ↩a ↩b

[4] Goldberg, David. "What Every Computer Scientist Should Know About Floating-Point Arithmetic". ACM Computing Surveys 23(1), 1991, 5-48. Shows that floating-point addition is not associative, so a summation's result depends on how the terms are grouped. registry ↩

[5] Pin, Jean-Eric. Varieties of Formal Languages. Plenum Press, 1986. Develops the free monoid, the syntactic monoid as a quotient by the syntactic congruence, regularity as finiteness of that monoid, and Schutzenberger's characterisation of star-free languages by aperiodicity. registry ↩

[6] Blelloch, Guy E. "Prefix Sums and Their Applications". School of Computer Science, Carnegie Mellon University, 1990. Defines the all-prefix-sums operation over a binary associative operator, with the exclusive prescan additionally requiring an identity element, so the value of a reduction is independent of how the input is partitioned across processors. registry ↩a ↩b

[7] Post, Emil L. "Recursive Unsolvability of a Problem of Thue". The Journal of Symbolic Logic 12(1), 1947, 1-11. Proves the word problem for a finitely presented semigroup, given as a Thue system on words over a finite alphabet, recursively unsolvable; the finitely presented monoid case is the same result on the free monoid with the empty word admitted. registry ↩

[8] Clifford, A. H., and G. B. Preston. The Algebraic Theory of Semigroups, Volume I. Mathematical Surveys 7. American Mathematical Society, 1961. Presents the bicyclic semigroup as the standard example of an infinite monoid generated by a pair with a one-sided inverse only, whose group of units is trivial. registry ↩

[9] Flajolet, Philippe, Eric Fusy, Olivier Gandouet, and Frederic Meunier. "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm". Discrete Mathematics and Theoretical Computer Science Proceedings AH (Conference on Analysis of Algorithms), 2007, 127-146. Gives a bounded-size sketch for distinct counting and states that under an arbitrary partitioning of the input it suffices to collect register values and apply a componentwise max, an associative and commutative merge with the empty sketch as unit. registry ↩