Radix Ordering on Words

81 Views Asked by At

Lothaire's Algebraic Combinatorics on Words gives the following definition of a total ordering, the radix order, on the set of finite words formed from an ordered alphabet $A$:

The radix order is defined by $x\leq y$ if $|x|<|y|$ or $|x|=|y|$ and $x=uax'$ and $y=uby'$ with $a,b$ letters and $a\leq b$.

However, this definition doesn't make sense to me, particularly the second part, as we could have $a=b$ and then have some the letter following $b$ be less than $a$, which would mean that this definition would also gives us $y\leq x$. I feel like this is a mistake, and it was intended as:

The radix order is defined by $x< y$ if $|x|<|y|$ or $|x|=|y|$ and $x=uax'$ and $y=uby'$ with $a,b$ letters and $a< b$.

However, the text's errata page gives no indication of this. Am I mistaken or misinterpreting the meaning here?

1

There are 1 best solutions below

2
On BEST ANSWER

Your interpretation of what the radix order was supposed to be is correct; you can see this from the last sentence in the paragraph defining the lexicographic order. My guess is that he wanted to define the radix order as a non-strict partial order and was a little careless. Your definition gives the strict version of the radix order; for the non-strict version that he apparently wanted, you need an extra alternative.

The radix order is defined by $x\le y$ if $|x|<|y|$, or $|x|=|y|$ and there are factorizations $x=uax'$ and $y=uby'$ with $a,b$ letters and $a<b$, or $x=y$.