Bernoulli measure on strings, and Thompson-Higman monoids.

DOI10.1007/s00233-011-9302-1zbMath1255.20050arXiv1004.5589MaRDI QIDQ766121

Jean-Camille 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 complexity; inverse monoids; Green relations; height functions; congruence-simple monoids; Thompson-Higman monoids

Mathematics Subject Classification ID

20M05: Free semigroups, generators and relations, word problems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

Cites Work

• The complexity of computing the permanent
• Monoid generalizations of the Richard Thompson groups.
• One-way permutations, computational asymmetry and distortion.
• Subtractive reductions and complete problems for counting complexity classes
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• The complexity theory companion
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item