title: Gap embedding theorems over well-quasi-orderings

<P>
 Iddo Tzameret 
<P>
abstract:
We review some results concerning well-quasi-order theory and the
Kruskal-Friedman type theorems. We then introduce our extension to
Kriz's result: For two labeled trees s and t we say that s is
embedded with gap into t if there is a 1-1 function from the vertices
of s into t which maps each edge in s to a unique path in t with
greater-or-equal labels. We show that finite trees are
well-quasi-ordered with respect to the gap embedding when the labels
are taken from an arbitrary well-quasi-ordering and each tree path can
be partitioned into a fixed natural  k, or less, comparable sub-paths.
This result generalizes both that of Kriz ['89] and that of Okada &
Takeuti's
quasi-ordinal-diagrams ['86], and is also optimal in the sense that
unbounded partiality yields a counter example.
<P>
Joint work with Nachum Dershowitz.