Bernoulli measure on strings, and Thompson-Higman monoids. (Q766121): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: John R. Donnelly / rank | |||
Property / reviewed by | |||
Property / reviewed by: John R. Donnelly / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1998067255 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1004.5589 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3653240 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: One-way permutations, computational asymmetry and distortion. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Monoid generalizations of the Richard Thompson groups. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3848243 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subtractive reductions and complete problems for counting complexity classes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3364262 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity theory companion / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4056178 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4774034 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3867972 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of computing the permanent / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:12, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bernoulli measure on strings, and Thompson-Higman monoids. |
scientific article |
Statements
Bernoulli measure on strings, and Thompson-Higman monoids. (English)
0 references
23 March 2012
0 references
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)].
0 references
Thompson-Higman monoids
0 references
Green relations
0 references
computational complexity
0 references
inverse monoids
0 references
congruence-simple monoids
0 references
height functions
0 references