Prefix Property:
Let's consider the set N* of finite sequences of natural numbers. Here are a few sequences:
x = (1, 2) y = (1, 2, 3) z = (2, 3)
The prefix property is a relation between sequences. In this example, x is a prefix of y because x appears at the beginning of y. We can denote this as x <p y. However, x is not a prefix of z, and z is not a prefix of y.
The set N* consists of finite sequences of natural numbers. Each element in N* is a sequence of natural numbers, which could be of varying lengths. For example, the set N* could include sequences like (1), (2, 3), (4, 5, 6), and so on.
In the context provided, x <p y denotes that sequence x is a prefix of sequence y. A prefix of a sequence is a subsequence that occurs at the beginning of the original sequence. For instance, if x = (1, 2) and y = (1, 2, 3, 4), then x is a prefix of y, denoted by x <p y.
Here are a few examples to better understand the concept:
- If x = (1) and y = (1, 3, 4), then x <p y because x is a prefix of y.
- If x = (2, 3) and y = (2, 3, 5, 6), then x <p y because x is a prefix of y.
- If x = (4, 5) and y = (1, 4, 5), then x is NOT a prefix of y, and x <p y does not hold.
We Can create the Partial Order lattice where we can find the every subset of the of GLB (meet) but may not find the every subset of LUB.