Bernoulli measure on strings, and Thompson-Higman monoids.

DOI10.1007/S00233-011-9302-1zbMATH Open1255.20050arXiv1004.5589OpenAlexW1998067255MaRDI QIDQ766121FDOQ766121

Authors: J.-C. Birget 

Publication date: 23 March 2012

Published in: Semigroup Forum (Search for Journal in Brave)

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.

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

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.

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)

Cites Work

• The complexity of computing the permanent
• Title not available (Why is that?)
• Subtractive reductions and complete problems for counting complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Codes and automata.
• Title not available (Why is that?)
• The complexity theory companion
• Title not available (Why is that?)
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• Monoid generalizations of the Richard Thompson groups.
• One-way permutations, computational asymmetry and distortion.

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)