Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [order-theory]

Questions about orders and their usage within formal contexts. This includes questions about both specific orders and orders in general.

Filter by
Sorted by
Tagged with
0 votes
1 answer
16 views

Algorithms for unordered vertices of the convex hull

For the sake of this question a "non-ordering" "set of vertices of convex hull" algorithm produces the collection of all points on the convex hull of its input without producing ...
worldsmithhelper's user avatar
4 votes
0 answers
54 views

Can `D = (D→ D)_⊥` be solved in the domain of DCPOs with monotonic functions?

A denotational semantic for the lambda calculus can be given by solving the domain equation $$ D \simeq [D →_c D]_\bot $$ in the category of $\omega$-complete CPOs, where $→_c$ denotes the space of $\...
Joachim Breitner's user avatar
2 votes
0 answers
129 views

A total order of rectangles related to containment

Suppose you have a set of rectangles $R_1,\dots,R_n$ in the plane, each described by an upper left point $p_1 \in \mathbb R^2$ and a lower right point $p_2 \in \mathbb R^2$, all pairwise different. ...
Jürgen Böhm's user avatar
3 votes
0 answers
65 views

Data structure for finding greatest lower bound with respect to a partial order

I have some partial order $\preceq \,\,\subset A \times A$, I'd like a data structure with the following operations: $Insert(a, x, T)$: add $(a, x)$ to the collection $T$ $Find(x, T)$: find the ...
Jake's user avatar
  • 3,810
3 votes
1 answer
88 views

Abstract Interpretation: Connection between soundness relation and a Galois connection

I am currently studying the paper "Abstract Interpretation Frameworks" by Cousot and Cousot from 1992 (https://doi.org/10.1093/logcom/2.4.511) to gain an understanding of the theory behind ...
cherrywoods's user avatar
1 vote
1 answer
52 views

Given a set of partial preorders, return one not covered by any in the set

Let $S$ be a set of partial preorders over a set $U$ ($\le$ is a preorder/quasiorder if $\forall x,y,z\in U$, $x\le x$ and $x \le y \land y \le z \implies x \le z$). We say that a partial preorder ...
andrepd's user avatar
  • 111
2 votes
0 answers
41 views

Given a vertex in a digraph, is there a standard term for (the vertices reachable from it) union (the vertices reaching it)?

Question in title. Looking for whether there is a term that is, if not widely understood, at least citeable to a source. This is equivalent to asking for the set of nodes that are comparable to the ...
Aaron Rotenberg's user avatar
1 vote
0 answers
68 views

Finding all minimal upper bounds in a partially ordered set

I have a partially ordered set of numbers, represented as a vector<set<int>> (e.g. if $2 \preceq 4$ in this order, then ...
Alexey Romanov's user avatar
1 vote
1 answer
53 views

Need help understanding Knuth's proof that: The set of all pure words is well-ordered by the relation >

In the paper linked below by Knuth and Bendix, theorem 1: The set of all pure words is well-ordered by the relation '$>$' has a proof that I can't seem to follow despite staring at it all day. I ...
frabrooks's user avatar
4 votes
1 answer
89 views

Arithmetical degree of suborders of Q

At the moment I am studying several questions about the arithmetical degree of some index-sets in relation to the standard-ordering on $\mathbb{Q}$. The situation is as follows: I fix some enumeration ...
Kasper's user avatar
  • 43
2 votes
0 answers
24 views

What's an efficient algorithm to check if a binary operator is residuated?

Assume the binary operator is given as a table/matrix, so constant time to compute $xy$. And likewise, assume the (relation giving rise to the) partially ordered set is also given as a table, or in ...
against very long user names's user avatar
2 votes
1 answer
128 views

Transitions between lexicographical orders

I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
Grigori's user avatar
  • 105
2 votes
0 answers
478 views

How to quickly determine whether a poset is a lattice?

Recently I encountered an interesting problem while studying discrete mathematics: Give the pseudo code to judge whether a poset $(S,\preceq)$ is a lattice, and analyze the time complexity of the ...
serenity's user avatar
3 votes
1 answer
247 views

Producing a total or partial order from an inconsistent relation

Imagine I want to construct a total order from a set of elements, $E$, but the comparison function produces results that are non-deterministic. I produce a list of element pairs (e, e) through ...
Nic's user avatar
  • 105
1 vote
1 answer
38 views

How do we know that $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$?

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.3 Data Flow Analysis says the following: The least solution. The ...
The Pointer's user avatar
1 vote
1 answer
67 views

Showing that $F$ is a monotone function

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.3 Data Flow Analysis says the following: The least solution. The ...
The Pointer's user avatar
0 votes
0 answers
435 views

Solve recursive function $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$

In one of my college assignments, I came up with the following recursive function which I'm asked to solve: $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$ I tried a change of the variable or the ...
Ashkan Khademian's user avatar
2 votes
1 answer
200 views

Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$

in one of my college assignments i came up with the following recursive function which I'm ask to solve: $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$ I could not use master method on it and it ...
Ashkan Khademian's user avatar
1 vote
0 answers
51 views

Algorithm suggestion to order data with specific condition

Suppose, we want to rearrange all possible $n$-bit binary strings (i.e., we have $2^{n}-1$ possible strings) in a 1-D array $X$; given that stings with smaller hamming distance should be placed as ...
user3862410's user avatar
2 votes
0 answers
36 views

What are all linear extensions of the product order of $\{1, \dots, M\} \times \{1, \dots, N\}$?

Note: I have read somewhere that finding all linear extensions of a partial order is in general a #P-complete problem (which apparently means difficult, and thus no closed form expression), but just ...
hasManyStupidQuestions's user avatar
1 vote
1 answer
2k views

Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?

I am working with the median-median algorithm or BFPRT algorithm and I seek to understand why would the partition of the array by $7$ blocks would work but with the $3$ fail? If we divide into ...
user13's user avatar
  • 209
3 votes
1 answer
81 views

Random observations of a total ordering, how much they tell us?

Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know ...
Ameer Jewdaki's user avatar
2 votes
2 answers
113 views

Inference of a measure for a decreasing chain

Set $I_n = \{0,\ldots,n-1\}$. Given integers $v_0,\dots,v_{n-1} \in \mathbb{N}$, find an integer $t>0$, a map $f:\mathbb{N} \times I_n \to \mathbb{N}^t$, and a well-founded order $>_t$ on $\...
user1868607's user avatar
  • 2,194
1 vote
1 answer
314 views

The sorting problem for partially ordered sets

I have two questions about sorting for posets, one easy and one hard: Easy: Suppose we have a set of objects and a partial order. Given any two objects such that $a \leq b$, we want to delete $b$ ...
Mike Battaglia's user avatar
5 votes
2 answers
2k views

Testing if a given DAG is a lattice

I am given a directed acyclic graph (DAG) with a unique source and sink. Is there an efficient way to test whether the partial order represented by this graph is a lattice? In other words, I need to ...
Mangara's user avatar
  • 238
0 votes
1 answer
1k views

Why is it that any graph traversal method can be described as pre-order, in-order, or post-order? What do those terms mean?

There are several graph traversal algorithms in computer science ( vis. depth first, breadth first, etc. ). Furthermore, each of these algorithms can be implemented in pre-order, in-order, and post-...
StudentsTea's user avatar
2 votes
1 answer
51 views

Maximal Elements in a Lower Set

I have a collection of objects, and a feasibility property for sets of objects which is slow to compute. If a set is feasible then so is any subset. For example, it could be whether the set of things ...
user29970's user avatar
3 votes
0 answers
146 views

Scott/Lawson topology for function space domain

Given two domains, $D_1$, $D_2$, already equipped with Scott (or Lawson) topology, the product domain $D=D_1\times D_2$ has the Tychonoff product topology, e.g., Mathematical Theory of Domains, ...
John Forkosh's user avatar
3 votes
0 answers
44 views

Original proof that orders eliminate deadlocks?

A well-known approach to eliminate the possibility of a deadlock when accessing exclusive ressources is enforcing a partial (or total) order in which the ressources may be requested. Which ...
dst's user avatar
  • 157
1 vote
2 answers
566 views

Path optimization in a DAG: maximizing number of least cost arcs

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
Charles G.'s user avatar
2 votes
1 answer
73 views

Total ordering of sets of fixed size

I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them): ...
Rufflewind's user avatar
2 votes
2 answers
2k views

Prove that any directed cycle in the graph of a partial order must only involve one node

So I have the question: Prove that any directed cycle in the graph of a partial order must only involve one node. So I know that a partial order must be transitive, antisymmetric, and reflective, ...
michael's user avatar
  • 47
10 votes
3 answers
6k views

Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?

Imagine I have an ordering on a bunch of elements like so: Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: $\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(...
Realz Slaw's user avatar
  • 6,191
17 votes
6 answers
10k views

What are lattices used for?

Wikipedia says: Complete lattices appear in many applications in mathematics and computer science Is it just referring to the fact that the standard Boolean algebra used in computation is a ...
Xodarap's user avatar
  • 1,538
6 votes
1 answer
666 views

Order preserving encoding of strings to numbers

I want to encode strings as real numbers while preserving order. The order of the strings is the lexicographic order (as used in phone books); the order of the numbers is the standard order. Is there ...
user12889's user avatar
  • 161
7 votes
2 answers
838 views

Are two elements always in a relation within a partially ordered set?

In a partially ordered set, am I always able to order two arbitrary elements out of the set? Or is it possible that two elements within the set have no order relation to each other? For example if ...
magnattic's user avatar
  • 547