Skip to main content
5 votes
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 ...
cody's user avatar
  • 14k
4 votes
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 ...
cody's user avatar
  • 14k
4 votes
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 ...
cody's user avatar
  • 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-...
M.Monet's user avatar
  • 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 ...
a3nm's user avatar
  • 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.
user53561's user avatar

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