Tag Info

9

If by Tarski's fix point theorem you mean the Knaster–Tarski fixpoint theorem, then it's widely applicable and very general. All you need is a complete lattice and a monotone function on the lattice. There are many rather different examples of those. Tarski-Knaster is for example used in the coinductive definition of bisimilarity. Another application is to ...

7

This is known as the "order maintenance" problem. There is a relatively simple solution using $O(1)$ amortized time for both queries and inserts. Now, by "relatively simple", I mean that you have to understand some building blocks, but that once you get those, the rest isn't hard to see. http://courses.csail.mit.edu/6.851/spring12/lectures/L08.html The ...

7

Instead of simple numbering, you could spread the numbers out over a large (constant sized) range, such as integer minimum and maximums of a CPU integer. Then you can keep putting numbers "in between" by averaging the two surrounding numbers. If the numbers become too crowded (for example you end up with two adjacent integers and there is no ...

6

It is called monotonicity with respect to the inclusion ordering of sets. More precisely, it is in this case increasing monotonicity since the order is preserved. If the order was reversed, it would be decreasing monotonicity. It can also be called direct monotonicity and reverse monotonicity, as increasing/decreasing seems used mostly for numeric ...

5

Yes there is, have a look at : Chen, Yangjun, and Yibin Chen. "On the Decomposition of Posets." Computer Science & Service System (CSSS), 2012 International Conference on. IEEE, 2012. and also this: Daskalakis, C., Karp, R. M., Mossel, E., Riesenfeld, S. J., & Verbin, E. (2011). Sorting and selection in posets. SIAM Journal on Computing, 40(3), ...

4

You can efficiently test whether $\preceq$ extends to a partial order using topological sorting. Form a directed graph with vertex set $X$ and with an edge $x \to y$ whenever we have $x \preceq y$ and $x \ne y$. Then $\preceq$ extends to a partial order if and only if this graph has no cycles, which can be checked in linear time (e.g., by topologically ...

4

Yes, it is. (Though you need to consider signed zero as well as NaNs.) For extra confirmation: So, the floating-point operator< does not form weak order and therefore does not form a total order. It is, however, a partial order. However, it cannot be extended to non-strict partial ordering <= because there's no (reflexive) equality for doubles (NaN !=...

4

A good first step is to construct a certain matrix corresponding to your relation, which I will let you figure out. Constructing this matrix takes time $O(|X|^2 + |S|)$ (or just $O(|S|)$, depending on your exact model). Given this, you can check antisymmetry in time $O(|X|^2)$, and transitivity in time $O(|X|^3)$. You can improve the running time of ...

4

There is an entire area, rank aggregation (in your case, partial rank aggregation) which deals with these issues. You can take a look at Dwork et al., Rank aggregation revisited and Ailon, Aggregation of partial rankings, $p$-ratings and top-$m$ lists and the pointers therein. There are many other relevant papers online.

3

You cannot avoid enumerating all elements. Consider the following two posets, with elements $x,y,z_1,\ldots,z_n$: $x,y < z_i$ for all $i$. $x,y < z_i$ for all $i < n$, and $z_n < x,y$. The first poset has two minima, and second only one. You can only tell the difference by enumerating over all elements. If there is a unique minimal element $z$,...

3

Your problem is the same as interval graph coloring. There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.

3

Your algorithm produces an infinite sequence of antichains whose size is unbounded. However, it doesn't produce a single antichain of infinite size. It is perfectly fine to specify an infinite chain by giving an algorithm that enumerates its members, and even more complicated constructions are possible (e.g. the priority method). However, the end result of ...

3

You can maintain a key-less AVL tree or similar. It would work as follows: The tree maintains an ordering on the nodes just as an AVL tree normally does, but instead of the key determining where the node "should" lie, there are no keys, and you must explicitly insert the nodes "after" another node (or in other words "in between" two nodes), where "after" ...

3

Consider the following problem. We are given $n$ sets $S_1,\ldots,S_n \subseteq \{1,\ldots,\log n\}$, and have to decide whether there are two disjoint sets among them. This problem is known as Orthogonal Vectors (OV), and it is conjectured that it cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon>0$ (on a RAM machine). See for example Chen ...

2

I'm assuming your partial orders are of the type "$a \leq b$" rather than of the type "$a < b$", though the proof is very similar to both cases. Each edge $a \to b$ in the graph corresponds to an inequality $a \leq b$. Now suppose you had a triangle $a \to b \to c \to a$. Such a triangle would imply $$a \leq b \leq c \leq a,$$ which has some implications ...

2

Hint: show that if $u$ is a substring of $v$ and $v$ is a substring of $w$ then $u$ is a substring of $w$.

2

Hints: First part: Suppose that $f$ is not one-to-one. That implies that $f(x) = f(y)$ for some $x \neq y$. Can $g \circ f$ be a bijection? Similar idea for the other half. Second part: We know that $f$ must be one-to-one and $g$ must be onto. So if $f$ and $g$ are not bijections, then $f$ must not be onto and $g$ must not be one-to-one. See how these two ...

2

As far as I know, it is an open problem whether one can do significantly better (in an asymptotic sense). This is known as the reachability query problem for DAGs. You want to do some precomputation, after which you can answer queries of the form Reachable$(u,v)$ (which should return true if $v$ is reachable via some path from $u$, i.e., if $u$ is an ...

2

Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, estimate the number of linear extensions efficiently.

1

This is a comment There is a confusion when you say that sorting is creating the correct total order. When sorting, the total order is input as the relation $\geq$. What sorting does is output the order-preserving map from the natural numbers $0,1,2,...$ to the totally ordered set (or multiset) that was input. Typically, when this is implemented the map is ...

1

This is a very well-known problem, known as topological sorting. Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such as this.

1

I think you mean partial order, as if you only have a preorder then there might not even exist any total order that is compatible with it. Your argument seems to be missing something about how you construct your topological sort, as it implies that any topological sort works, which you disproved yourself. In your example $x,y,x',y'$ could be a topological ...

1

One approach is to sort the sets by increasing size, then repeatedly perform the following: take the first set in the list, output it, and remove from the list all supersets of it. This will output all of the minimal sets. The running time is $O(nk)$ set comparisons plus $O(n \log n)$ steps for sorting, where $n$ is the number of sets you have and $k$ is ...

1

It is pleasing to see such a nice algorithm. Your algorithm is correct for all inputs except possibly for two corner cases. For example, if we have input = [['A', 1], ['B', 2], ['A', 2], ['B', 3]], then your algorithm will not produce the expected A<=B. For example, if we have input = [['A', 1], ['B', 1], ['A', 1], ['B',1] or input = [['A', 1], ['A', 1]...

1

Take a worst case scenario. The set is built out of pairs of objects $a_i, b_i$ where $a_i < b_i$ and there exists no order between $a_i < b_j$ when $i\neq j$. This means that to know whether you can delete an element you need to check it against every other element resulting in a quadratic general case. The best data structure to avoid that is ...

1

This is the dynamic reachability problem for DAGs, where you only need to handle vertex/edge insertion (but not deletion). It's sometimes known as incremental reachability or incremental DAG reachability. There's lots written in the research literature on the subject. Here are some pointers to get you started: https://cstheory.stackexchange.com/q/18787/...

1

Your solution looks good to me, except that your lookup arrays are a bit handwavy: What happens if the set contains negative numbers? Or what if it contains an extremely large number ($\gg n^2$), so that the arrays would need to be massive? To address this, I'd suggest creating just a single lookup table, that instead of mapping from values to indices, maps ...

1

I think I am able to solve it. First, have a lookup array for each sequence where array[element] = element's position in sequence [O(1)]. Phrased another way, this algorithm will find all "successors" for each of the elements in the first sequence. Finding successors for each element will take O(n) time. For i in range(0,n): initialize ...

1

Apparently, we're given a collection of equations of the form $$|x_i - x_j| = c_{i,j},$$ where the $c_{i,j}$ are given and $x_1,\dots,x_n$ are the unknowns to solve for. We want to look for a valid solution that satisfies all of the equations, and where the values of $x_1,\dots,x_n$ are a permutation of $1,2,\dots,n$. The kind of algorithm to use will ...

Only top voted, non community-wiki answers of a minimum length are eligible