Automatic transformation of XML namespaces/Implementation/Precedences

From Wikiversity
Jump to: navigation, search

See also an alternative solution.

TODO: Add parentheses to the formulas.

Theorem Minimal strict partial order containing a given irreflexive relation is equal to transitive closure of this relation if such strict partial order exists. It exists iff the given relation is acyclic.

Proof That it exists if the given relation is acyclic, is obvious. Accordingly Wikipedia, transitive closure of a directed acyclic graph is a strict partial order. Evidently there is no strict partial order containing the given relation which is less than it. So it the minimal.

Let us denote the strict partial order for subclass relation (of precedences) (can be calculated by the above theorem).

Let us denote the directed acyclic (remove the loops if any) graph of specified "higher than" precedences.

Let us denote the strict partial order of precedences (to be calculated).

Theorem can be calculated by the following algorithm: [FIXME: When does exist?]

Let be the transitive closure of .

Let = .

Start loop.

Let . If then it is the answer. [TODO: do one rather than two multiplications at a time. FIXME: Should it be instead: ?]

Let . If then it is the answer.

End loop.

Proof ??