Questions tagged [order-theory]
Questions about orders and their usage within formal contexts. This includes questions about both specific orders and orders in general.
35
questions
4
votes
0
answers
50
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 $\...
- 290
2
votes
0
answers
123
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.
...
- 121
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 ...
- 3,790
3
votes
1
answer
77
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 ...
- 161
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 ...
- 111
2
votes
0
answers
37
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 ...
- 3,473
1
vote
0
answers
66
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 ...
- 3,127
1
vote
1
answer
52
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 ...
- 13
4
votes
1
answer
88
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 ...
- 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 ...
- 1,250
2
votes
1
answer
127
views
Transitions between lexicographical orders
I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
- 95
2
votes
0
answers
403
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 ...
- 21
3
votes
1
answer
192
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 ...
- 105
1
vote
1
answer
34
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 ...
- 203
1
vote
1
answer
61
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 ...
- 203
0
votes
0
answers
372
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 ...
- 250
2
votes
1
answer
199
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 ...
- 250
1
vote
0
answers
50
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 ...
- 141
1
vote
0
answers
31
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 ...
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 ...
- 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 ...
- 531
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 $\...
- 2,184
1
vote
1
answer
305
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$ ...
- 837
5
votes
2
answers
1k
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 ...
- 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-...
- 320
2
votes
1
answer
50
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 ...
- 23
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, ...
- 305
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 ...
- 157
1
vote
2
answers
530
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 ...
- 37
2
votes
1
answer
71
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):
...
- 153
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, ...
- 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(...
- 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 ...
- 1,538
6
votes
1
answer
649
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 ...
- 161
7
votes
2
answers
800
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 ...
- 537