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

From Wikiversity
Jump to navigation Jump to search

DAG is an abbreviation of directed acyclic graph.

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

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

.

Proposition Axiomatic precedence system can be instead characterized by the formula . (FIXME: in this formula has two different meanings.)

Proof Equivalently transforming, the formula we get:

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

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 and constitute a precedences system together with a given partial order . (FIXME: I (yet) cannot rule out that there may be multiple minimal orders!)

The algorithm[edit]

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 , you add an edge .

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 , to test whether , you do a reachability query: you check whether is reachable from in the graph (e.g., with DFS or BFS). If you're given a new relationship , you add the edge to the dag; also, you check whether (i.e., whether is reachable from ), 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 represent the "is subclass of" relation, and represent the "is higher than" relation. Then your condition is: if and and then .

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 . We'll represent the partial order with a second dag; I'll write its edges using . Any time we an edge (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 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 , we'll create two more artificial elements and , with extra relationships according to the following rules: if , then and ; and if , then . These encode the condition you want to enforce, as if and , then we'll have and thus 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 is added, add also edge .
  • Any time a vertex is added, add also edge .
  • Any time you add an edge , also add the edge .
  • Any time you add an edge , also add the edge .

You now get two dags that interact: whenever you add an edge to the dag for , 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 , it doesn't trigger adding any more edges.)

First, we will prove . Let for example and (or we can have any number of steps). Then we have and and consequently .

Let now prove . Let for example and (or we can have any number of steps). Then we have , thus .

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 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.