Faster hardware does not cancel exponential search
Mackworth opens with a rebuke to the artificial-intelligence mood of his time. If a program consumes resources like kⁿ, doubling the machine permits only a fixed additive increase in the number of words, regions or clauses it can handle.
The target class is constraint satisfaction. A finite set of variables must receive values from finite domains while unary and binary predicates hold simultaneously. The task can be stated as an existential formula: find a tuple whose individual values satisfy their unary conditions and whose pairs satisfy every relevant relation. Generate-and-test, theorem proving and backtracking are possible solution schemes.
Backtracking improves on blind generation because a failed partial assignment discards an entire Cartesian subspace. It instantiates variables in order, tests every predicate as soon as all its variables are bound, and returns to the most recent variable with an untried value when a test fails. The mechanism is sound, but it can spend most of its time learning the same fact repeatedly.
The paper calls this pathological repetition “thrashing”, following Bobrow and Raphael. Mackworth's response is not simply a cleverer variable order. It is to extract implications from the constraint specification before and between branching decisions, so a contradiction discovered locally becomes persistent shared state rather than a transient failure at one leaf of a search tree.
The network view makes that state visible. Node i denotes variable vᵢ and carries domain Dᵢ. A loop represents the unary predicate Pᵢ. A directed arc (i,j) represents Pᵢⱼ; the reverse arc represents the converse relation, so support is directional even when the underlying constraint is described once. A complete assignment is a selection of one value per node satisfying the whole labelled graph.
Worked example 1 · a timetable as a network
Let Lecture, Room and Tutor be variables. Their domains list available periods, rooms and staff. “Room has capacity” is unary if a single lecture is fixed; “Lecture and Tutor share a period” and “two lectures do not overlap” are binary. The graph displays which local facts can restrict which choices.
Causal probe 1 · double the processor budget
If work is 2ⁿ, twice the budget adds only one variable at the same runtime. An algorithmic reduction in the explored space compounds; a constant hardware multiplier does not change the exponent.
The same contradiction can be paid for again and again
The paper diagnoses three levels of avoidable failure. Each later definition of consistency is the positive state that prevents one of them.
First, a domain may contain a value that violates its own unary predicate. Backtracking can instantiate that value under many different earlier assignments and rediscover the same immediate failure each time. Removing it once is node filtering.
Second, a value a in Dᵢ may have no compatible value anywhere in a later neighbour's domain Dⱼ. Search may traverse all combinations of variables placed between i and j before proving that a can never work, and may repeat that proof under many assignments to variables placed before i. Removing a when its lack of support is visible is arc filtering.
Third, values a at i and b at j may be directly permitted, yet no value x at an intermediate node k supports both relations Pᵢₖ(a,x) and Pₖⱼ(x,b). A search tree can discover this unsupported pair only after irrelevant intervening choices, then rediscover it in several subtrees. Removing the pair from the relation between i and j is path filtering.
Mackworth's five-node ordering example is intentionally small enough to print, but its failure tree is already long. The lesson is structural: changing the order may move the pain without eliminating the latent contradiction. The network should propagate the reason for failure independently of whichever prefix happened to expose it.
Worked example 2 · one unsupported colour
Variable A has colours {red,blue}; neighbour B has {red}; their relation requires different colours. A=red has no support in B, so every search prefix containing it must fail. Arc revision deletes red from A once instead of waiting for repeated leaf failures.
Causal probe 2 · reorder variables only
A favourable order may reveal the unsupported value sooner on this instance. It does not turn that fact into a reusable domain deletion, and another constraint pattern can make the new order pathological. Scheduling and inference are different remedies.
Consistency is a quantified condition, not a vague coherence score
Each consistency level says that every currently permitted object has a witness. The object grows from a value, to a directed value-neighbour relation, to a pair connected by a whole path.
Node i is node consistent exactly when every x in Dᵢ satisfies Pᵢ(x). A network is node consistent when this holds everywhere. Because unary tests do not depend on other domains, NC-1 simply filters each node once.
Arc (i,j) is arc consistent when every unary-permitted x in Dᵢ has at least one unary-permitted y in Dⱼ satisfying Pᵢⱼ(x,y). Direction matters. All A values may have a B support while some B value lacks any A support; then (A,B) is consistent and (B,A) is not. A network is arc consistent only when every directed arc passes.
A path (i₀,i₁,…,iₘ) is path consistent when each directly permitted endpoint pair x,y can be extended along that path by intermediate values z₁,…,zₘ₋₁ satisfying every node and adjacent relation. Paths may repeat nodes. Different occurrences of a repeated node may receive different values in this local witness, a subtlety that distinguishes path tests from a global assignment.
These properties are nested as forms of local support but do not generally equal global solvability. An arc-consistent triangle of two-colour “not equal” constraints has support along every single edge and still has no complete colouring. Stronger propagation can expose more contradictions, but constructing the fully minimal equivalent network is a harder problem.
Worked example 3 · direction exposes asymmetry
Let A={1,2}, B={2}, and permit A<B. Value 1 in A has support 2 in B but value 2 in A does not, so REVISE(A,B) removes 2. In the reverse relation, B=2 has support A=1. The paired directed checks answer different questions.
Causal probe 3 · confuse local witnesses with one global witness
A value may be supported by y on one arc and by a different incompatible z on another. Arc consistency does not require those separate supports to extend to one complete tuple. Reporting “solution found” from local support alone is unsound.
A value survives only while a neighbour can support it
All three arc algorithms are built from REVISE. Its code is short; the scheduling problem around it is where their differences lie.
REVISE((i,j)) scans each x in Dᵢ. If no y in Dⱼ satisfies Pᵢⱼ(x,y), x is deleted from Dᵢ and the procedure reports that a deletion occurred. Immediately afterwards arc (i,j) is consistent. But this property is not permanent: later deletion from Dⱼ may remove the last support of some x and make (i,j) inconsistent again.
Support is existential. One compatible y is enough to keep x, and the algorithm need not commit variable j to that y. The deletion is safe because every complete solution assigning x to i would have to assign some value to j; if none of its current values is compatible, no complete solution uses x. Thus filtering reduces representation while preserving every solution.
A deletion flows opposite the revised arc. If REVISE(k,m) shrinks Dₖ, arcs (p,k) pointing into k may lose supports and need reconsideration. Arc (m,k) is excluded from immediate requeueing: values removed from Dₖ were precisely those without support in Dₘ, so their removal cannot deprive a Dₘ value of the particular support it actually had in Dₖ.
Termination follows from monotonicity and finiteness. Domains only lose values and contain finitely many. Revisions may repeat, but successful ones cannot occur forever. At a fixed point, every remaining directed arc has support under the final domains.
Worked example 4 · support disappears later
A={1,2}, B={2,3}, and A<B. Both A values initially survive: 1 has 2 or 3, and 2 has 3. If another neighbour later deletes 3 from B, A=2 loses its only support. Arc (A,B) must return to the queue.
Causal probe 4 · revise the undirected edge once
Checking that each A value has a B partner does not check that each B value has an A partner. Treating a binary constraint as one undirected test silently leaves directional inconsistency.
The inference is stable; the scheduling becomes selective
Mackworth presents three routes to the same arc-consistent fixed point. They differ in which revisions are reconsidered after a domain changes.
AC-1 first achieves node consistency, then repeatedly revises every directed arc. One successful deletion causes another complete pass, even though most arcs cannot have been affected. It is easy to state and easy to prove, but its worklist is the entire graph on every iteration.
AC-2 follows the spirit of Waltz's scene-labelling filter. It introduces nodes in order and sends waves of revision through already introduced neighbours. Two queues distinguish the current frontier from the next. The schedule exploits locality, but its control is more elaborate and a cycle longer than two can cause an arc to wait in both queues.
AC-3 abandons the requirement that one node introduction be fully propagated before the next. It begins with all directed arcs in a queue. Pop any (k,m); if revision shrinks Dₖ, enqueue every relevant incoming (i,k) that is not already waiting and does not immediately point back from m. Queue order can alter efficiency, but not the final arc-consistent closure produced by these monotone deletions.
The conceptual progression is reusable. First define a local correction that is sound. Then identify exactly which other checks can change truth after that correction. A dependency-aware worklist avoids global rescans without changing the fixed point. AC-3 became memorable not because queues were new, but because the queue encodes the causal footprint of lost support.
Worked example 5 · a three-arc cascade
Revising (B,C) removes B=blue. Only arcs whose head is B can lose support, such as (A,B) and (D,B). If (A,B) then removes A=green, incoming arcs to A enter the queue. Unconnected arcs are not rescanned.
Causal probe 5 · enqueue every arc after deletion
Correctness survives, but the procedure collapses towards AC-1's waste. The key optimisation is not using a queue in name; it is restricting the queue to checks whose inputs changed.
Intersection and composition transmit constraints
Arc revision can treat a binary predicate as code. Path revision needs to delete particular allowed pairs, so Mackworth represents every finite relation as a Boolean matrix.
Rows of Rᵢⱼ correspond to values of vᵢ and columns to values of vⱼ. Entry one means the pair is permitted. The converse relation is the transpose. Unary permission can be placed on the diagonal of Rᵢᵢ, with off-diagonal entries zero.
Intersection combines simultaneous constraints point by point: an entry survives only when both relation matrices contain one. Composition transmits a relation through an intermediate variable. Pair (a,c) belongs to RᵢₖRₖⱼ when some b makes both (a,b) and (b,c) permissible. Algebraically this is Boolean matrix multiplication, replacing multiplication by AND and summation by OR.
An induced relation through k can tighten a direct relation: Rᵢⱼ becomes Rᵢⱼ ∩ (RᵢₖRₖⱼ). A directly legal endpoint pair is deleted when no intermediate value witnesses the two-step path. This is the pair-level analogue of deleting a domain value with no neighbour support.
The five-queens example supplies geometry. Each column is a variable and its row is the value. Direct relations prohibit equal rows and diagonals. A pair of queen placements may satisfy their mutual constraint but fail to admit any legal placement in an intervening column; composition exposes that indirect restriction before a complete board is built.
Worked example 6 · Boolean composition
R_AB permits (1,x) and (2,y). R_BC permits (x,red) and (y,blue). Their composition permits (1,red) and (2,blue). If the direct A-C relation forbids (2,blue), intersection removes that pair from the network even though each individual arc still contains alternatives.
Causal probe 6 · use ordinary arithmetic multiplication
Counting paths is not the required semantics. Composition asks whether at least one intermediate witness exists. Boolean OR collapses one or many witnesses to permission; arithmetic counts would change the relation type.
The complete local picture is still not the global solution
Once indirect relations can be computed, the tempting goal is a minimal equivalent network: every directly permitted pair participates in at least one complete solution.
Two networks are equivalent when they have the same satisfying tuples. A network is minimal when no remainder of the network further restricts any pair permitted by a direct relation. One brute-force construction is obvious: enumerate every solution, then retain exactly the value pairs that appear in at least one. But this central problem inherits the difficulty of finding solutions.
Mackworth invokes a restricted graph three-colourability construction to argue that computing the minimal network in polynomial time would imply P=NP. Domains need only three values and each node only a bounded number of non-vacuous relations. Local filtering cannot be assumed to make arbitrary global combinatorics easy.
The judicious target is a path-consistent equivalent network. Montanari's theorem states that in a complete constraint graph, if every length-two path is consistent, the network is path consistent. The closure therefore repeatedly intersects each relation Rᵢⱼ with the relation induced through every k until no pair changes.
Path consistency is stronger than arc consistency in what it records: it can remove an endpoint pair while leaving both endpoint values individually viable. Yet it is still a relaxation of minimality. The paper's architecture matters here: acknowledge the hard central problem, compute a sound polynomial local closure, and then interleave it with case analysis when closure alone does not decide.
Worked example 7 · an allowed pair that no solution uses
A=1 and C=3 may satisfy the direct A-C relation. If neither value of B is compatible with both, the pair is deleted by path consistency. Each of A=1 and C=3 may survive separately through other partners, so arc domains alone cannot record this fact.
Causal probe 7 · equate path consistency with minimality
Path consistency guarantees extension along each path using witnesses that may differ between paths. Minimality requires one complete tuple satisfying all relations simultaneously. Replacing the stronger global quantifier with many local existentials overstates the closure.
Monotone pair deletion reaches an order-independent closure
PC-1 is the direct repeated-sweep algorithm. PC-2 is its selective worklist refinement, parallel to the move from AC-1 to AC-3.
PC-1 copies the network and, for every intermediate k and endpoints i,j, replaces Yᵢⱼ with Yᵢⱼ ∩ YᵢₖYₖₖYₖⱼ. It repeats until a whole pass makes no change. Intersection makes the process monotone: ones can become zeros but never return. At termination every length-two path is consistent, so Montanari's theorem gives path consistency.
The first form stores more network copies than necessary and performs many computations guaranteed to do nothing. Updating one matrix in place can accelerate convergence. Symmetry avoids nearly half the work. But the substantial improvement again comes from causality: when Yᵢⱼ shrinks, reconsider the length-two paths that use arc (i,j) or (j,i).
PC-2's queue initially contains every relevant triple (i,k,j). REVISE computes Z=Yᵢⱼ ∩ YᵢₖYₖₖYₖⱼ. If Z differs, replace Yᵢⱼ and add RELATED PATHS, excluding triples whose revision is predictably null. The ordering of queued paths affects work but not the closure.
Mackworth compares PC-1 with transitive-closure and shortest-path dynamic programs. Those algorithms may need only one ordered pass because their composition distributes over the combining operation. Boolean relational composition does not generally distribute over intersection in the required way, so iteration cannot simply be wished away. Algebraic law determines schedule.
Worked example 8 · one pair deletion causes a distant check
If path i-k-j deletes (a,b) from Yᵢⱼ, a path i-j-m may lose its only witness for an endpoint pair between i and m. PC-2 queues that related path. A path on disjoint variables reads no changed relation and remains asleep.
Causal probe 8 · process each triple exactly once
A later relation deletion can invalidate support used by an earlier triple. Unless the algebra guarantees a one-pass order, refusing to requeue leaves an inconsistent fixed point masquerading as completion.
Propagation prunes; branching completes
The general problem-solving paradigm alternates deterministic constraint manipulation with explicit cases. Each branch adds a constraint, propagates it, and becomes a child in an OR problem graph.
A case split creates p copies of the current network and adds one of p mutually exhaustive case constraints to each. Their disjunction is a tautology, so no solution disappears from the union of branches. Consistency procedures then prune each copy. A branch is solved when every variable has one remaining value and all relations hold; a discovered empty domain or relation proves that branch unsatisfiable.
This encompasses Fikes's alternation of Boolean constraint manipulation with instantiation and Burstall's bisection of domains. It also avoids treating propagation as merely a preprocessing phase. A case decision creates new local consequences, so the network should be closed again before another decision expands the tree.
Applications in the paper include cryptarithmetic, Instant Insanity, magic squares, n-queens, clique detection, graph problems, continuous spatial planning where relations need not be Boolean matrices, and several vision systems. Waltz's junction labels are node values; consistent edge interpretations are binary constraints. Physical separation in a picture can limit how far a deletion propagates, explaining observed near-linear behaviour in some scenes without guaranteeing it generally.
Mackworth also proposes consistency as a default retrieval mechanism for AI languages and semantic networks. A query such as “find a large rectangle touching a triangle and inside a circle” is itself a constraint network. Rather than enumerate rectangles blindly, propagation can begin from the unique circle and its containment relation. The desired “smart” control emerges from generic local inference, not a hand-written backtracking order for each database.
Worked example 9 · branch, propagate, branch again
A four-queen network remains non-singleton after AC-3. Split on Q₁∈{1,2} versus Q₁∈{3,4}; close each branch. If the first empties a neighbour domain, discard it immediately. Continue only in the surviving OR branch.
Causal probe 9 · run propagation only once at the root
Every case constraint shrinks a domain or relation and can trigger new deletions. Failing to propagate after branching forfeits precisely the shared inference that prevents thrashing inside the new subtree.
Equivalent reduction is not universal tractability
The central achievement is a unified framework for local consistency algorithms and their use. The paper does not claim that AC-3 or PC-2 solves every constraint network without search.
Every deletion needs a witness argument: an unsupported value or pair cannot appear in any solution, so removing it preserves the solution set. This equivalence is more important than the surface reduction in size. An aggressive filter that deletes a valid solution is not “more consistent”; it has changed the problem.
Conversely, survival is not proof of global feasibility. Local procedures can reach a non-empty fixed point on an unsatisfiable cyclic network. Their value is to make implicit contradictions explicit cheaply and repeatedly, reducing later case analysis. A complete solver must recognise when propagation is inconclusive and branch without overclaiming.
Complexity depends on representation, graph density, domain size, queue order and application structure. Waltz's picture examples may propagate within a physical object because T-junctions decouple regions, but that domain-specific locality is not a theorem for arbitrary graphs. The paper explicitly contrasts empirical behaviour with worst-case analysis.
Modern names can obscure the 1977 contribution. AC-3 is now taught as a standard CSP routine, yet the paper places it within a broader account: three maladies, three consistency concepts, relation matrices, path closure, minimal-network hardness, worklist refinement, applications, and an alternation of inference with search. The system of ideas is larger than one pseudocode block.
Worked example 10 · arc-consistent but impossible
Three variables each have {red,blue}; every pair must differ. Each colour has support across every edge, so AC-3 deletes nothing. Yet no two-colour assignment satisfies the triangle. The fixed point is locally supported and globally impossible.
Causal probe 10 · treat an empty queue as a solution
An empty queue means no scheduled local revision can delete more. It certifies arc or path consistency of the current representation, not a complete satisfying tuple. Search may still be necessary.
Evidence boundary
Network consistency formalises constraint propagation. It does not determine which real-world constraints are legitimate, whose preferences define a domain, or whether a locally consistent institutional arrangement is desirable.
Change five relations and watch support propagate
Five controls choose one of four binary relations on a cycle A-B-C-D-E-A, giving 4⁵=1,024 networks. The laboratory applies fixed unary restrictions, AC-3 and complete length-two path closure, while an independent enumerator preserves the exact global solution set for audit.
Running solution-preservation audit…
Running fixed-point audit…
Running relation-closure audit…
Worked example 11 · deletions are directional events
The trace names the directed arc popped, the value removed and the incoming arcs requeued. Switch A-B from different to equal: a domain change may travel around the cycle in a new direction even when the graph drawing is unchanged.
Causal probe 11 · inspect solution count only
Two relation settings can have the same number of solutions and very different propagation. The domain and pair ledgers reveal whether local closure found the global restriction early or left it for enumeration.
Claims, premises and audit handles
| Claim | Premise | Audit handle |
|---|---|---|
| REVISE safely removes x from Dᵢ. | No current y in Dⱼ satisfies Pᵢⱼ(x,y). | Enumerate all complete solutions and confirm none assigns x to i. |
| AC-3 finishes arc consistent. | Finite domains; all affected incoming arcs are requeued after a deletion. | At queue exhaustion, test every remaining value for support on every directed arc. |
| Queue order does not change the closure. | Revisions are monotone, contracting and fairly scheduled. | Run alternative worklist orders and compare final domains. |
| Length-two closure gives path consistency. | The relation graph is completed and Montanari's theorem applies. | For every i,k,j and allowed endpoint pair, find an intermediate support. |
| The minimal network is not cheaply obtained in general. | Arbitrary finite binary CSPs include the restricted three-colourability construction. | Keep minimality distinct from arc and path closure. |
| Constraint manipulation may precede each case. | Case constraints are exhaustive across OR branches and propagation preserves solutions. | Compare the union of branch solution sets with the parent set. |
Fidelity, teaching and execution review
Review one: scholarship. The reconstruction preserves the finite unary/binary CSP formulation, directed converse arcs, the three sources of thrashing, exact node/arc/path definitions, non-simple path qualification, NC-1, REVISE, AC-1, Waltz-inspired AC-2, AC-3's affected-arc queue, relation matrices, Boolean intersection and composition, induced relations, minimal-network definition and hardness argument, Montanari's length-two theorem, PC-1, RELATED PATHS, PC-2, OR problem graphs and the application boundaries.
Review two: teaching and execution. Ten accessible SVGs each carry a unique title, description, caption and source scope; animation is supplementary and disabled under reduced-motion preference. Twelve worked examples and twelve causal probes test directionality, witness scope, fixed points, relation algebra, minimality and propagation after branching. The laboratory enumerates 1,024 relation networks, compares all filtering with an independent exact solution set, and validates both arc and length-two path closure.
AI-telltale and evidence review. The prose avoids saying that a network “knows” a value is impossible. Deletion is always licensed by a missing support witness. “AC-3” is not presented as a universal solver, “path consistent” is not inflated into globally satisfiable, and modern CSP terminology is used only to clarify structures already explicit in 1977.
Accessibility and scope review. Figures use shape and text alongside colour; every control has a label; dynamic results appear in an aria-live region; tables scroll on narrow screens; all layouts collapse cleanly at 900 and 600 pixels. The paper's examples in vision and programming languages are reported as applications and proposals, not converted into claims about cognition or experience.
Twelve cards for rebuilding the framework
An intelligent search space can be revised before it is traversed
Backtracking remembers choices, but naive backtracking forgets reasons. It can learn that one prefix fails and still reconstruct the same contradiction under another prefix. Network consistency stores a more general result: this value has no support, or this pair has no extension. The deletion is reusable across every branch that inherits the network.
This is a form of abstraction. A failed complete assignment contains many details irrelevant to its cause. REVISE projects the failure onto the smallest directed relation that witnesses it. Path revision projects it onto an endpoint pair. The more general explanation prunes more future cases, provided its quantified support test is sound.
The queue is causal attention. AC-1 looks everywhere after any change; AC-3 directs work to constraints that read the changed domain. PC-2 applies the same principle to changed pair relations. Efficient inference depends not only on what operation is valid, but on an explicit dependency map of what could have become invalid.
The alternation with case analysis also offers a mature picture of bounded reasoning. Local closure extracts cheap consequences; branching spends combinatorial effort only when inference stalls; the new decision then seeds more propagation. Neither pure deduction nor pure enumeration dominates. Their cycle is the algorithm.
Worked example 12 · a reason outlives the branch that exposed it
A failed schedule reveals that Monday for Lecture A has no compatible room at all. Recording only “this partial schedule failed” helps one subtree. Removing Monday from A's domain explains and prevents every recurrence, while preserving any schedule that could actually work.
Causal probe 12 · delete without retaining the relation that justified it
The solver may still run, but auditability collapses. A reviewer cannot distinguish a sound lack-of-support deletion from a bug or an unstated policy rule. Intelligent pruning needs both contraction and a recoverable reason.
Boundary statement
Constraint propagation exhibits structured, goal-directed information processing. It is not evidence that the process has phenomenal consciousness, preferences of its own, or moral standing. Those claims require different observations.
From adversarial cutoffs to relational propagation
Canon 0076 studied Knuth and Moore's alpha-beta analysis. A bound created in one branch proves that some later siblings cannot affect an adversarial choice. Canon 0077 shifts from a tree of alternatives to a network of simultaneous obligations. A missing support in one relation deletes a value and wakes the constraints that depended on it.
Both papers turn omission into a proof. Alpha-beta omits descendants after a threshold certificate; AC-3 omits values after a support certificate. The difference is persistence: an alpha-beta cutoff belongs to one search window, while a domain deletion changes the residual problem inherited by every later case.
Canon 0078 moves back to tree search with Richard E. Korf's “Depth-first iterative-deepening” (1985), asking how breadth-first optimality and depth-first memory can be combined by repeatedly increasing a depth bound.
What this companion adds
This companion reconstructs the paper's ten-section progression rather than isolating AC-3. It begins with the exponential-resource warning and the three backtracking maladies; binds each to a formal consistency condition; follows the scheduling refinements from full sweeps to causal queues; then lifts value filtering to Boolean relation algebra and path closure.
The distinction between a path-consistent network and a minimal equivalent network remains explicit. The graph-colouring hardness argument limits what local propagation can promise, and the OR problem graph shows how Mackworth intended consistency to cooperate with case analysis. Applications in puzzles, spatial planning, vision and AI-language retrieval retain their own caveats.
Ten bespoke animated diagrams, twelve worked examples, twelve causal probes, twelve memory cards and a verification ledger expose the proof obligations. The executable laboratory audits 1,024 constraint cycles against exhaustive solutions, verifying that AC-3 and path closure remove no satisfying tuple and that their reported fixed points meet the definitions.
Primary and contextual sources
- Alan K. Mackworth, “Consistency in Networks of Relations”, Artificial Intelligence 8(1), 99–118 (1977). Publisher DOI.
- Ugo Montanari, “Networks of Constraints: Fundamental Properties and Applications to Picture Processing”, Information Sciences 7, 95–132 (1974).
- David L. Waltz, Generating Semantic Descriptions from Drawings of Scenes with Shadows, MIT AI-TR-271 (1972).
- Richard E. Fikes, “REF-ARF: A System for Solving Problems Stated as Procedures”, Artificial Intelligence 1, 27–120 (1970).
- Michael R. Garey, David S. Johnson and Larry Stockmeyer, “Some Simplified NP-Complete Problems”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 47–63 (1974).
- Stephen Warshall, “A Theorem on Boolean Matrices”, Journal of the ACM 9, 11–12 (1962), used by Mackworth for the closure comparison.