Skip to main content

Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers
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 ...
1 vote
1 answer
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 ...
13 votes
2 answers
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 ...
15 votes
3 answers
1k views

Complexity of topological sort with constrained positions

I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$. A topological sort of $G$ is a bijection $f$ from the vertices ...
10 votes
1 answer
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$. ...
10 votes
2 answers
533 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 ...
2 votes
1 answer
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 ...
5 votes
1 answer
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 ...
11 votes
2 answers
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 ...
5 votes
0 answers
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)$ ...
6 votes
1 answer
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 ...
2 votes
1 answer
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$ ...
10 votes
0 answers
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 ...
2 votes
0 answers
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 ...
1 vote
0 answers
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 ...
3 votes
0 answers
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)$...
5 votes
0 answers
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 ...
3 votes
1 answer
133 views

Hook length formuli and their invariance properties?

Let $P = (V,\leq_P)$ be a poset, and for each $x \in V$ let $x^P = \{ y \in V : x \leq_P y \}$. A well-known property of certain posets (forests, Young diagrams) is the existence of a simple hook ...
5 votes
0 answers
144 views

Structures admitting directed sums and directed products?

Some structures have a property of closure by a "sum" or "product" operation. Given a family of structures $(S_i)_{i \in I}$, we can then define a new structure denoted by $\sum_{i \in I} S_i$, resp. $...
4 votes
0 answers
96 views

Residual for transitive hull

I work in the algebra $R$ of reflexive, transitive relations over some set $S$, ordered by subset inclusion. This is a complete lattice, with intersection as g.l.b. and transitive hull as l.u.b., i.e. ...
10 votes
0 answers
451 views

Illustrative Examples of Tarski's Fixed Point Theorems

I have come across many informal examples that provide a physical illustration for Brouwer's fixed point theorem (some due to Brouwer himself). A person walks from the bottom of a hill to the top. ...
5 votes
1 answer
989 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. ...
16 votes
4 answers
451 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 ...
13 votes
1 answer
443 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 ...
31 votes
5 answers
4k 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 ...
8 votes
2 answers
387 views

Sufficient conditions to guarantee unique fixpoint (not unique least/greatest fixpoint) for monotone functions on complete lattice

Tarski's fixpoint theorem states, that the fixpoints of a monotone operator on a complete lattice is a complete lattice. By consequence, we have a unique greatest fixpoint and unique least fixpoint ...
13 votes
1 answer
272 views

A question on linear extensions of partial orders

If you're given a collection of partial orders, topological sort will tell you if there's an extension of the collection to a total order (an extension in this case is a total order consistent with ...
1 vote
0 answers
103 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 ...
7 votes
1 answer
906 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 Poset-...
4 votes
1 answer
308 views

Measures of "correlation" between two orderings

An easy question perhaps? Taking a (fictional) concrete example, let's say I have two ranking methods for HTML documents: PageRank and HITS. I derive an ordered list over the same set of documents ...
17 votes
4 answers
804 views

Applications of metric structures on posets/lattices in theoryCS

Since the term is overloaded, a brief definition first. A poset is a set $X$ endowed with a partial order $\le$. Given two elements $a,b \in X$, we can define $x \vee y$ (join) as their least upper ...