[asQuirreL]

To build on the pedantry, make would be traversing a restricted form of directed acyclic hyper-graph, no? The edges are between sets of vertices to a single vertex.

I found these structures cropping up alongside Horn clauses, and Context-Free Grammars in interesting ways. In this case, viewing make rules as Horn clauses allows us to use a variant of Horn-SAT to find the minimum set of files we have to produce to build a rule, which is interesting to think about, and reason about.

This article felt as though it was food for thought and not really trying to push any particular idea too hard. In any case, I found it interesting as it found parallels to the sorts of structures I found when exploring various algorithms for Context-Free Grammars (such as pruning, or detecting erasable non-terminals, which can both be described in terms of Horn-SAT).

[mbreese]

Well, you have a large graph defined with multiple end points, so the DAG itself doesn't necessarily point to any single vertex. Only once you define which endpoint you want does it collapse.

[asQuirreL]

Well, if you want file `X` then you can ensure you find the minimal set of files to produce `X` from your given rules using Horn-SAT by adding `and X` to the Horn Formula representation of the build rules. Pretty neat!