Defining an order on strings from an alphabet given an order on the alphabet itself

Question

Let $A$ be a finite nonempty alphabet, and let $\leq$ be a partial order on $A$. I want to define a partial order on $A^*$, the Kleene closure of $A$, based on the partial order on the alphabet itself. I know that when the partial order $\leq$ is in fact linear, then we simply have the lexicographic order. So my question really is, what is the analogue of the lexicographic order for general finite partially ordered alphabets?

Answer 1

The usual "first point of difference" idea works even if the alphabet is only partially ordered. Given a partial order $(A;\le)$, we can define an induced partial order $\trianglelefteq$ on $A^*$ as follows: $\sigma\trianglelefteq\tau$ iff

• $\sigma$ is an initial segment of $\tau$ (possibly $\sigma=\tau$), or

• there is some smallest $n$ such that $\sigma(n)$ and $\tau(n)$ exist and are distinct, and for this $n$ we have $\sigma(n)\le\tau(n)$.

(In particular, note that this gives rise to the following situation: if $\sigma(n)$ and $\tau(n)$ are $\le$-incomparable, where $n$ is the "first point of difference," then $\sigma$ and $\tau$ are $\trianglelefteq$-incomparable.)