# Tag Info

Accepted

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

Every simplification order is indeed a well-partial order because of this simple statement: If $R$ is a well-quasi order, and $S$ is a partial order, and $R\subseteq S$, then $S$ is a well-partial ...
• 14k
Accepted

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

Surely, you want $s_1 < s_2$ if there is a $t$ such that $s_1.t < s_2.t$ and $s_1.u \leq s_2.u$ for every other field $u$. That, at least, gives you a well-founded order. But there are many ...
• 14k
Accepted

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

Here's a nice property of WQOs: If $R$ is a WQO on terms, and $S$ is another transitive relation such that $$R\ \subseteq\ S$$ Then $S$ is a WQO Proof: Let $t_1,\ldots, t_n,\ldots$ be an ...
• 14k
1 vote

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

Co-worker here. We haven't solved it yet, but here are a few remarks (in case it gives anyone an idea, because we are stuck). The main thing we have for now is a partial result on so-called crown-...
• 1,431
1 vote

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

With my coauthor, we have just posted a preprint which studies this problem more generally for regular languages. In the case of finite groups, we claim that the problem is tractable (in NL) in the ...
• 9,677
1 vote

### Lattice problems

Here is a link, may be it can help you. http://fc.isima.fr/~nourine/publications.php M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.

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