Bernoulli measure on strings, and Thompson-Higman monoids.

DOI10.1007/S00233-011-9302-1MaRDI QIDQ766121zbMATH OpenOpenAlexFDO

Authors J.-C. Birget

Publication date 23 March 2012

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.5589

zbMATH Keywords

computational complexitycongruence-simple monoidsGreen relationsheight functionsinverse monoidsThompson-Higman monoids

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The Bernoulli measure on strings is used to define height functions for the dense R- and L-orders of the Thompson-Higman monoids M_{k,1}. The measure can also be used to characterize the D-relation of certain submonoids of M_{k,1}. The computational complexity of computing the Bernoulli measure of certain sets, and in particular, of computing the R- and L-height of an element of M_{k,1} is investigated.

Review text

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)].

Recommendations

• The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
• Uniform and Bernoulli measures on the boundary of trace monoids
• The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
• Completions in measure of languages and related combinatorial problems
• Monoid generalizations of the Richard Thompson groups.

Cites work

• Codes and automata.
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• scientific article; zbMATH DE number 4218075 (Why is no real title available?)
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3670685 (Why is no real title available?)
• scientific article; zbMATH DE number 3470638 (Why is no real title available?)
• scientific article; zbMATH DE number 3448564 (Why is no real title available?)
• Monoid generalizations of the Richard Thompson groups.
• One-way permutations, computational asymmetry and distortion.
• Subtractive reductions and complete problems for counting complexity classes
• The complexity of computing the permanent
• The complexity theory companion
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY

Cited in

(4)

• A simple non-bisimple congruence-free finitely presented monoid.
• A countable series of bisimple \(\mathcal H\)-trivial finitely presented congruence-free monoids.
• A countable family of finitely presented infinite congruence-free monoids
• The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.

This page was built for publication: Bernoulli measure on strings, and Thompson-Higman monoids.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q766121)