The partial-order tag has no wiki summary.
8
votes
0answers
128 views
How fast can we compute the set inclusion poset of a set family?
Given a set family $\mathcal{F}$ of subsets of a universe $U$.
Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$.
I am looking for a data-structure that will allow me to ...
2
votes
1answer
80 views
Verifying consistency of strict and non-strict partial orders constraints
I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables ...
4
votes
1answer
182 views
Efficient representation of set of partial order
I guess that notions I describe are already well known, may be by combinatorician, but I do not know their name or any book/article about them. So if you have a link/title I would love to read it.
...
13
votes
4answers
285 views
Worst number of questions needed to learn a monotonic predicate over a poset
Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by ...
2
votes
0answers
101 views
Generalizing linear interpolation to posets
Assume that I have an array $A$ of $n$ numerical values where some are known and some are unknown (with $A[0]$ and $A[n-1]$ assumed to be known). If I want to estimate an unknown value $A[i]$, a ...
11
votes
1answer
207 views
Minimal elements of a monotonic predicate over the powerset $2^{|n|}$
Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking ...
1
vote
0answers
91 views
What effect would using different types of orders have on a binary search tree?
Recently, I was coding a comparator function for use in a set backed by a binary search tree, and the set kept saying that it didn't contain elements that I had previously added to it. I eventually ...
21
votes
5answers
3k views
Binary search generalizations for posets?
Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.
EDIT: I'm interested in minimizing the number of evaluations of P.
What ...
4
votes
2answers
203 views
Number of subsets on a set with partial order
Given a set $S$ with strict partial order $<$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a<b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are ...
6
votes
1answer
241 views
On finding a chain decomposition of a Partial Order
I am reading a paper by Daskalakis et al. entitled "Sorting and Selection in Posets". http://arxiv.org/abs/0707.1532
In that paper it is presented an enhancement to the algorithm ...
2
votes
1answer
311 views
My exact divide-conquer algorithm for counting antichain in a poset?
This post is a little lengthy, thank your for your patience for reading. ^_^
As known, counting antichains in a poset is #P-complete, so it is NP-hard to get the exact answer. Following is my simple ...
11
votes
1answer
251 views
Is counting maximal cliques in an incomparability graph #P-complete?
This question is motivated by a MathOverflow question by Peng Zhang. Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs ...
9
votes
1answer
292 views
Lattice problems
There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...).
I am curious what work specific to ...
6
votes
1answer
171 views
reference for lexicographic path ordering
Can you recommend a good reference for reading about lexicographic/recursive path orderings?
I'm currently reading about lpo's in Chapter 2 of the Handbook of Automated Reasoning, 'Resolution Theorem ...
1
vote
0answers
267 views
Well Defined Ordering Relations in Object Oriented Type Systems [closed]
In any Object-Oriented type system the type relation of two objects A and B can be characterized in exactly one of the following ways:
A has the same type as B
A is a subtype of B
B is a subtype of ...
5
votes
2answers
195 views
Partially Ordered CFG
I'm looking for work about partially ordered context-free grammars. I've found one paper, which seems to simplify the problem too much (in addition to some technical mistakes, as far as I can tell). ...
2
votes
1answer
344 views
Extension of a partial order to a total of partitions of a weak alternating automaton
My problem is this: given a weak alternating automaton and its partitions, and given a partial order on these partitions, how do we extend the partial order to a total order?
The partitions of weak ...
14
votes
0answers
283 views
The complexity of checking whether two DAG have the same number of topological sorts
This problem is highly related to the CNF one.
Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".
...
11
votes
1answer
490 views
Positive topological ordering, take 2
This is a followup to David Eppstein's recent question and is motivated by the same problems.
Suppose I have a dag with real-number weights on its vertices. Initially, all of the vertices are ...
37
votes
5answers
1k views
Positive topological ordering
Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...
