Bernoulli measure on strings, and Thompson-Higman monoids. (Q766121)

In this well-written and self-contained paper, the author uses the Bernoulli measure on strings to define height functions for the dense \(\mathcal R\)-orders and \(\mathcal L\)-orders of the Thompson-Higman monoids \(M_{k,1}\). The author investigates the computational complexity of computing the \(\mathcal R\)-height and \(\mathcal L\)-height of an element of \(M_{k,1}\). Included in the paper is an appendix which contains a proof that the monoids \(M_{k,1}\) and \(\text{Inv}_{k,1}\) are congruence-simple. This completes the proof of a result that was stated, but not proven in an earlier paper of the author [J. Pure Appl. Algebra 213, No. 2, 264-278 (2009; Zbl 1191.20063)].