View source for Automatic transformation of XML namespaces/Implementation/Precedences

See also [[Automatic transformation of XML namespaces/Implementation/Precedences/Old answer|an alternative solution]].

'''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. [[wikipedia:Transitive_closure#In_graph_theory|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 <math>C</math> the strict partial order for subclass relation (of precedences) (can be calculated by the above theorem).

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

Let us denote <math>H</math> the strict partial order of precedences (to be calculated).

'''Theorem''' <math>H</math> can be calculated by the following algorithm: [FIXME: When does <math>H</math> exist?]

Let <math>E</math> be the transitive closure of <math>h</math>.

Let <math>F</math> = <math>E</math>.

Start loop.

Let <math>G=E\cup (C^{-1}\circ E\circ C)</math>. If <math>G=E</math> then it is the answer. [TODO: do one rather than two multiplications at a time. FIXME: Should it be instead: <math>G=E\cup (E\cup C^{-1}\circ E)\circ C</math>?]

Let <math>F=G\cup (E\circ G)</math>. If <math>F=G</math> then it is the answer.

End loop.

'''Proof''' ??

[[Category:Automatic transformation of XML namespaces]]