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 complexityGreen relationsheight functionsinverse monoidscongruence-simple monoidsThompson-Higman monoids

Mathematics Subject Classification ID

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

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.

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

• 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?)
• Codes and automata.
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• Monoid generalizations of the Richard Thompson groups.
• One-way permutations, computational asymmetry and distortion.
• Subtractive reductions and complete problems for counting complexity classes
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• The complexity of computing the permanent
• The complexity theory companion

Cited in

(4)

• A countable series of bisimple \(\mathcal H\)-trivial finitely presented congruence-free monoids.
• A simple non-bisimple congruence-free finitely presented monoid.
• 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)