Automatic transformation of XML namespaces/Implementation/Precedences/Old answer

DAG is an abbreviation of directed acyclic graph.

Precedences system $U$ is a set of precedences where a precedence is a nonempty set (of transformations). A precedence $A$ is higher that another precedence $B$ (denoted $A>B$) if every element of $A$ is higher than every element of $B$.

I will call axiomatic precedences system a pair of nonstrict partial order $\subseteq$ (generated by a given DAG) and the strict partial order $>$ and conforming to the formula:

$A>B\Rightarrow \forall X\in U,Y\in U:(X\subseteq A\land Y\subseteq B\Rightarrow X>Y)$.

Proposition Axiomatic precedence system can be instead characterized by the formula ${\mathord {\ngtr }}\supseteq (\subseteq \circ \ngtr \circ \supseteq )$. (FIXME: $\supseteq$ in this formula has two different meanings.)

Proof Equivalently transforming, the formula we get:

$A>B\Rightarrow \forall X\in U,Y\in U:(X\subseteq A\wedge Y\subseteq B\Rightarrow X>Y)$

$A>B\Rightarrow \forall X\in U,Y\in U:(\neg (X\subseteq A\wedge Y\subseteq B)\vee X>Y)$

$A>B\Rightarrow \forall X\in U,Y\in U:\neg ((X\subseteq A\wedge Y\subseteq B)\wedge X\ngtr Y)$

$A>B\Rightarrow \neg \exists X\in U,Y\in U:(X\subseteq A\wedge Y\subseteq B\wedge X\ngtr Y)$

$A>B\Rightarrow \neg A(\subseteq \circ \ngtr \circ \supseteq )B$

${\mathord {>}}\subseteq \neg (\subseteq \circ \ngtr \circ \supseteq )$

${\mathord {\ngtr }}\supseteq (\subseteq \circ \ngtr \circ \supseteq )$ $\square$

Proposition Every axiomatic precedences system is isomorphic to a set-valued precedences system. (The reverse is obvious.)

Proof https://math.stackexchange.com/a/2600852/4876 $\square$

Proposition If a pair of DAGs does not generate a system of precedences, then adding new edges to these DAGs cannot make it to generate a system of precedences.

Proof ??

We need to find the minimal order $>$ which contains a given (by the DAG) order $>_{0}$ and constitute a precedences system together with a given partial order $\subseteq$. (FIXME: I (yet) cannot rule out that there may be multiple minimal orders!)

The algorithm

An (edited) copy of a deleted https://cs.stackexchange.com answer by the user D.W.:

Let me first suggest what data structure to use to store these partial orders. I suggest you represent each partial order as a dag (directed acyclic graph), via its " Hasse diagram. In other words, you build a dag to represent the relationships that are given: if you're given $a\geq b$, you add an edge $a\to b$.

The partial order represented by a dag is the transitive closure of that dag. You never need to explicitly build the transitive closure. Rather, given $c,d$, to test whether $c\geq d$, you do a reachability query: you check whether $d$ is reachable from $c$ in the graph (e.g., with DFS or BFS). If you're given a new relationship $a\geq b$, you add the edge $a\to b$ to the dag; also, you check whether $a\geq b$ (i.e., whether $a$ is reachable from $b$), as if so, then this is no longer a partial order and there doesn't exist any partial order consistent with the relationships you've been given.

That covers how to store and manage these relationships.

Now let's consider how to handle the condition connecting these two partial orders. Let $\succeq$ represent the "is subclass of" relation, and $\geq$ represent the "is higher than" relation. Then your condition is: if $A_{1}\succeq A$ and $B_{1}\succeq B$ and $A>B$ then $A_{1}>B_{1}$.

You can maintain the partial orders to ensure that condition holds. We'll represent the $>$ partial order with one dag; I'll write its edges using $\to$. We'll represent the $\succ$ partial order with a second dag; I'll write its edges using $\hookrightarrow$. Any time we an edge $A\to B$ (in the dag for $>$), we'll update it to represent all the other relationships implied by your condition. Naively, we could do this by iterating over all possible values of $A_{1},B_{1}$ and adding more edges to the dag for $>$ as required by the condition. However, that would be a bit slow. I'll describe a more efficient way to achieve the same result.

Let's triple the number of nodes in the dag for $>$, i.e., triple the number of elements. For each element $A$, we'll create two more artificial elements $A^{*}$ and $A_{*}$, with extra relationships according to the following rules: if $A_{1}\succeq A$, then $A_{1}\geq A^{*}$ and $A_{*}\geq A_{1}$; and if $A>B$, then $A^{*}>B_{*}$. These encode the condition you want to enforce, as if $A_{1}\succeq A$ and $B_{1}\succeq B$, then we'll have $A_{1}\geq A^{*}>B_{*}\geq B_{1}$ and thus $A_{1}>B_{1}$ will be implied.

So instead of enforcing your condition, we'll enforce my replacement rule. In particular, we enforce my rule as follows:

• Any time a vertex $A$ is added, add also edge $A_{*}\to A^{*}$.
• Any time a vertex $A$ is added, add also edge $A\hookrightarrow A^{\ast }$.
• Any time you add an edge $A\to B$, also add the edge $A^{*}\to B_{*}$.

• Any time you add an edge $A_{1}\hookrightarrow A$, also add the edge $A_{*}\to A_{1}$.

You now get two dags that interact: whenever you add an edge to the dag for $\succ$, you have to add some edges to the other dag as well. (Fortunately, the changes don't cascade: the two rules above only apply to unstarred elements, so when you add the edge $A_{1}\to A^{*}$, it doesn't trigger adding any more edges.)

First, we will prove $A>C\Rightarrow A^{\ast }>C_{\ast }$. Let for example $A\to B$ and $B\to C$ (or we can have any number of steps). Then we have $A^{\ast }\to B_{\ast }$ and $B^{\ast }\to C_{\ast }$ and consequently $A^{\ast }>C_{\ast }$.

Let now prove $A_{1}\succ A\Rightarrow A_{1}\succ A^{\ast }$. Let for example $A_{1}\hookrightarrow C$ and $C\hookrightarrow A$ (or we can have any number of steps). Then we have $A\hookrightarrow A^{\ast }$, thus $A_{1}\succ A^{\ast }$.

Now this gives a clean solution to your problem. Any time you learn about a new relationship, add it to the dag and make any additional changes required by the above rules. Any time you add an edge to the dag, immediately check to make sure the dag remains a partial order. If you want to know whether two elements are related, do a reachability query in the appropriate dag.

Since you never have to build the transitive closure explicitly, this should be pretty space-efficient. Adding edges to the dag can be done in $O(1)$ time. Reachability queries might take linear time, but perhaps that is OK.

If you want to make the reachability queries faster, then there are algorithms and data structures for that as well. You want algorithms for incremental reachability in a dag (also called dynamic reachability for dags). This has been studied in the literature. It's possible that one of those algorithms might be more efficient, but I'm not sure, and it will probably also be more complex to implement. See, e.g., https://cstheory.stackexchange.com/q/18787/5038, https://cstheory.stackexchange.com/q/25298/5038, Efficiently determine relative ordering between two elements in a PO-set, How to evaluate relations in a DAG?, https://cstheory.stackexchange.com/q/29/5038.