# Questions tagged [order-theory]

The tag has no usage guidance.

31 questions
Filter by
Sorted by
Tagged with
106 views

### What conditions are necessary (and sufficient) for the order-dual of a Scott-Ershov domain to also be a domain?

That is, considering the underlying poset of a domain, when does the order-dual poset also comprise a domain? Below's a little, not strictly necessary, elaboration of that question. Usual ...
• 275
1 vote
124 views

### How to prove that Supremum preorder coincides with Hoare preorder?

Given a complete lattice $(L, \sqsubseteq)$ and a basis of completely $\sqcup$-irreducibles $B_L \subseteq L$, such that $\forall l \in L$, $l=\sqcup\{b \in B_L\ |\ b \sqsubseteq l\}$. I mean: Hoare ...
359 views

### Lighting up all elements of a poset by toggling upsets

I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. ...
• 9,269
59 views

### Ordering sequences containing bitvectors for size-change termination

I'm working with the size-change termination principle to show program termination. In the system I work with, there is a so-called bit-vector ordering that goes as follows: Given two sequences of ...
• 1,017
100 views

### If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?

The homeomorphic embedding relation for trees as I understand it is a well-quasi-order (wqo) on trees when the label of a node determines the number of children of that node, and there are a finite ...
• 615
94 views

### Series-parallel extension of a partial order respecting a given total order

Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length. An $O(n^3)$ ...
118 views

### Is every well-founded simplification order a well-partial order?

I'm contemplating the proof of Kruskal's Tree Theorem, as presented in the book "Term Rewriting and All That." They use it to prove that every simplification order is well-founded: first by showing ...
• 455
49 views

### Two preorders with same glb

I have a set $S$ with two preorders $\mathord{\le}_1,\mathord{\le}_2\subseteq S\times S$ which a priori are unrelated. Let $\equiv_1$ and $\equiv_2$ be the induced equivalences (i.e., $x\equiv_1 y$ ...
288 views

### Determining what can be achieved by a permutation of elements of a noncommutative group

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
• 9,269
4k views

### Lexicographically minimal topological sort of a labeled DAG

Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
• 9,269
108 views

### Completeness of the quotient of the power set lattice of a partial order induced by the Hoare pre-order

Let $(P,\le)$ be a partially ordered set and $\preceq$ the Hoare pre-order on its subsets, i.e. for $X,Y\subseteq P$, $X\preceq Y$ iff $\forall x\in X:\exists y\in Y:x\le y$. Let $\sim$ be the ...
138 views

### Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
• 9,269
205 views

### Exact catchup point between SGH and FGH of ordinals?

An ordinal hierarchy is a way to assign a function $f_{\alpha} : \mathbb{N} \rightarrow \mathbb{N}$ to each (recursive) ordinal $\alpha$. The corresponding functions are expected to be monotone and ...
• 1,292
140 views

### Convolution products in partial semigroups

A partial semigroup (or PSG) consists of a set $X$ and of a partial composition law $*$ defined over $X$, that is to say: (1) $x*y$ is not always defined, (2) if $(x*y)*z$ is defined, so is $x*(y*z)$...
• 1,292
1 vote
123 views

### Spectrum of a variety: a possible connection btw ordinals and structures?

Consider a variety of algebras $\mathbb{V} = \mathbb{V}(\sigma,\tau)$ which consists of the set of algebras defined over a fixed signature $\sigma$ and satisfying a set of identities $\tau$. We may ...
• 1,292