<p>The paper <a href="http://arxiv.org/abs/0707.1532" rel="nofollow">"Sorting and Selection in PoSets" by Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008</a> which describes a dynamic representation of PoSets based on antichains.</p>

<p>You might also be interested in the paper <a href="http://arxiv.org/abs/1204.1957" rel="nofollow">"Succinct Posets" by Munro, Nicholson, 2012</a> recently released on Arxiv and in the bibliography therein. Their data-structure is static but I assume that the next step is to have a dynamical data-structure.</p>

CC BY-SA 3.0
2017-11-15T11:24:47.077Z
Sorting and Selection in Posets is great to get an idea what is needed for a data structure, but the algorithms are assuming $\mathcal{O}(1)$ tagging of elements in the poset (e.g. exactly the problem we want to solve in the first place!) to compute the relation between two elements in $\mathcal{O}(1)$ after building up the data structure in $\mathcal{O}(qn)$ queries.

So, the paper assumes queries of the relation between two elements to be expensive and mapping elements of posets to be trivial, whereas map data structures typically assume the converse of the former to solve the latter.
Sebastian Graf
CC BY-SA 3.0
2017-11-15T11:27:13.090Z
Having maps represented as a (minimal) decomposition of chains is good insight. Preserving that invariant through deletes is what is tricky, though.
Sebastian Graf
CC BY-SA 3.0
2012-04-14T14:22:39.717Z
2016-02-17T20:10:59.583Z
2016-02-17T20:10:59.583Z
J.y B.y
<p>Have you looked at <a href="http://arxiv.org/abs/1010.1316" rel="nofollow">Heeringa et al's "Searching in Dynamic Tree-Like Partial Orders"</a>? They give a dynamic data structure for the predecessor problem on posets. It is designed for a RAM, but you can represent arrays as balanced binary trees and incur only a $O(\lg n)$ multiplicative overhead while making the structure purely functional.</p>

CC BY-SA 3.0
2017-08-10T20:15:16.670Z
Note this only cover 'tree-like' partial orders, e.g. meet-semilattices, where all elements less than or equal to some element `e` form a chain.
Sebastian Graf
CC BY-SA 3.0
2012-04-15T21:58:06.660Z
2016-02-17T20:11:13.493Z
2016-02-17T20:11:13.493Z
jbapple
<p>I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable.</p>

<p>One problem with hashtables is that two equal elements can be represented differently, and I do not have access to a hashing function consistent with equality.</p>

<p>Comparing two elements can be a lengthy process so it would be interesting to minimize comparisons. If needed, it is possible to memoize calls to the comparison operator. I realize now that I will only need to store antichains (or let's assume so).
More precisely, the operations I will need to perform are as follows:</p>

<ul>
<li>Remove an element from the antichain;</li>
<li>Try to add an element. If the element is smaller than a member, do not add it, otherwise, add it and remove every element smaller than it.</li>
</ul>

<p>I can also bound every element by two integers, so that if I know that $i_1 &lt; a &lt; i_2$ and $i_3 &lt; b &lt; i_4$, then knowing $i_2 &lt; i_3$ instantly gives me $a &lt; b$. Of course, $i_2 \not&lt; i_3$ does not mean $a \not &lt; b$... Finding integer bounds is a relatively cheap operation in comparison to a full blown element comparison.</p>

CC BY-SA 3.0
2011-10-07T04:49:01.887Z
I think we need to know more to inteligently answer your question. Are you storing the elements and the partial order is easily computed? Or are you also storing the partial order in some sort of a lookup table? How do you intend to use the partial order? Are you hoping to use it the same way that linear order is used to store sets (for example in search trees)?
Andrej Bauer
CC BY-SA 3.0
2011-10-07T06:37:59.873Z
Now that I realized I will only have antichains, I'm not sure there is anything better than the naïve solution of storing the results in a list. If so, sorry for the trouble!
Abdallah
CC BY-SA 3.0
2011-10-07T15:13:06.017Z
If you think your question is now moot, maybe you should flag it for deletion/closing ?
Suresh Venkat
CC BY-SA 3.0
2011-10-07T22:10:54.257Z
Any two elements in the set will be incomparable, but this doesn't mean that the naive representation is the best you can do. For example, consider finite multisets ordered by inclusion (= integers ordered with divisibility): there is a lot of potential for optimisation, depending on your data representation (using cardinality, using the support set, …). These optimisations will strongly depend on the nature of the order relation. Then there's the separate issue of deciding whether it's worth keeping information about now-deleted elements: are you going to compare them often to new additions?
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2011-10-07T22:44:27.077Z
Ok, thank you. So I added some information (the integer bounding possibility) that could lead to optimizations.
Abdallah
CC BY-SA 3.0
2012-04-16T07:03:12.537Z
The integer bounds confused me for a while -- if they're not totally ordered, how can they be comparable to integers?  But then I remembered Conway games: http://arxiv.org/abs/math.CO/0410026
Jeffε
CC BY-SA 3.0
2012-04-17T00:06:23.773Z
You guessed my field of application. I am indeed working on Combinatorial Game Theory.
Abdallah
<ds.data-structures><functional-programming><sorting>
What persistent data structure for a set of partially ordered elements?
Abdallah
# What persistent data structure for a set of partially ordered elements?

(Asked by: username_0 on 2011-10-06)

I need to store sets of elements of type a. Type a is partially ordered, so comparing $a\_1$ and $a\_2$ can return smaller, greater, equal or incomparable.

One problem with hashtables is that two equal elements can be represented differently, and I do not have access to a hashing function consistent with equality.

Comparing two elements can be a lengthy process so it would be interesting to minimize comparisons. If needed, it is possible to memoize calls to the comparison operator. I realize now that I will only need to store antichains (or let's assume so).
More precisely, the operations I will need to perform are as follows:

* Remove an element from the antichain;
* Try to add an element. If the element is smaller than a member, do not add it, otherwise, add it and remove every element smaller than it.

I can also bound every element by two integers, so that if I know that $i\_1 < a < i\_2$ and $i\_3 < b < i\_4$, then knowing $i\_2 < i\_3$ instantly gives me $a < b$. Of course, $i\_2 \not< i\_3$ does not mean $a \not < b$... Finding integer bounds is a relatively cheap operation in comparison to a full blown element comparison.

**Tags:** ds.data-structures, functional-programming, sorting

> **Comments:**
> **username_1**: I think we need to know more to inteligently answer your question. Are you storing the elements and the partial order is easily computed? Or are you also storing the partial order in some sort of a lookup table? How do you intend to use the partial order? Are you hoping to use it the same way that linear order is used to store sets (for example in search trees)?  
> **username_0**: Now that I realized I will only have antichains, I'm not sure there is anything better than the naïve solution of storing the results in a list. If so, sorry for the trouble!  
> **username_2**: If you think your question is now moot, maybe you should flag it for deletion/closing ?  
> **username_3**: Any two elements in the set will be incomparable, but this doesn't mean that the naive representation is the best you can do. For example, consider finite multisets ordered by inclusion (= integers ordered with divisibility): there is a lot of potential for optimisation, depending on your data representation (using cardinality, using the support set, …). These optimisations will strongly depend on the nature of the order relation. Then there's the separate issue of deciding whether it's worth keeping information about now-deleted elements: are you going to compare them often to new additions?  
> **username_0**: Ok, thank you. So I added some information (the integer bounding possibility) that could lead to optimizations.  
> **username_4**: The integer bounds confused me for a while -- if they're not totally ordered, how can they be comparable to integers?  But then I remembered Conway games: http://arxiv.org/abs/math.CO/0410026  
> **username_0**: You guessed my field of application. I am indeed working on Combinatorial Game Theory.  

---

## 2 answers

### Answer by username_5 on 2012-04-14. Score: 10

The paper ["Sorting and Selection in PoSets" by Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008](http://arxiv.org/abs/0707.1532) which describes a dynamic representation of PoSets based on antichains.

You might also be interested in the paper ["Succinct Posets" by Munro, Nicholson, 2012](http://arxiv.org/abs/1204.1957) recently released on Arxiv and in the bibliography therein. Their data-structure is static but I assume that the next step is to have a dynamical data-structure.

> **Comments:**
> **username_6**: Sorting and Selection in Posets is great to get an idea what is needed for a data structure, but the algorithms are assuming $\mathcal{O}(1)$ tagging of elements in the poset (e.g. exactly the problem we want to solve in the first place!) to compute the relation between two elements in $\mathcal{O}(1)$ after building up the data structure in $\mathcal{O}(qn)$ queries.  So, the paper assumes queries of the relation between two elements to be expensive and mapping elements of posets to be trivial, whereas map data structures typically assume the converse of the former to solve the latter.  
> **username_6**: Having maps represented as a (minimal) decomposition of chains is good insight. Preserving that invariant through deletes is what is tricky, though.  

---

### Answer by username_7 on 2012-04-15. Score: 5

Have you looked at [Heeringa et al's "Searching in Dynamic Tree-Like Partial Orders"](http://arxiv.org/abs/1010.1316)? They give a dynamic data structure for the predecessor problem on posets. It is designed for a RAM, but you can represent arrays as balanced binary trees and incur only a $O(\lg n)$ multiplicative overhead while making the structure purely functional.

> **Comments:**
> **username_6**: Note this only cover 'tree-like' partial orders, e.g. meet-semilattices, where all elements less than or equal to some element `e` form a chain.  

---

