Longest common subsequence: Difference between revisions
Content added Content deleted
m (Removed duplicate Examples section.) |
m (Wordsmithing.) |
||
| Line 16: | Line 16: | ||
If i1 ≤ i2 and j2 ≤ j1 (or i2 ≤ i1 and j1 ≤ j2) then neither m1 < m2 nor m1 > m2 are possible; and m1, m2 are ''incomparable''. |
If i1 ≤ i2 and j2 ≤ j1 (or i2 ≤ i1 and j1 ≤ j2) then neither m1 < m2 nor m1 > m2 are possible; and m1, m2 are ''incomparable''. |
||
Defining (#) to denote this case, we write m1 # m2. Because the underlying product-order is strict, m1 == m2 (''i.e.'', i1 == i2 and j1 == j2) implies m1 # m2. Thus, the (<>) operator is the inverse of (#). |
Defining (#) to denote this case, we write m1 # m2. Because the underlying product-order is strict, m1 == m2 (''i.e.'', i1 == i2 and j1 == j2) implies m1 # m2. m1 <> m2 implies m1 ≠ m2, ''i.e.'', that the two tuples differ in some component. Thus, the (<>) operator is the inverse of (#). |
||
Because the product-order is strict, m1 <> m2 implies m1 ≠ m2, ''i.e.'', that the two tuples differ in some component. |
|||
Given a product-order over the set of matches '''M''', a chain '''C''' is any subset of '''M''' where m1 <> m2 for every pair of distinct elements m1 and m2 of '''C'''. Similarly, an antichain '''D''' is any subset of '''M''' where m1 # m2 for every pair of distinct elements m1 and m2 of '''D'''. |
Given a product-order over the set of matches '''M''', a chain '''C''' is any subset of '''M''' where m1 <> m2 for every pair of distinct elements m1 and m2 of '''C'''. Similarly, an antichain '''D''' is any subset of '''M''' where m1 # m2 for every pair of distinct elements m1 and m2 of '''D'''. |
||