The R- and L-orders of the Thompson-Higman monoid M_k,1 and their complexity.
From MaRDI portal
Publication:3580222
Abstract: We study the monoid generalization M_{k,1} of the Thompson-Higman groups, and we characterize the R- and the L-preorder of M_{k,1}. Although M_{k,1} has only one non-zero J-class and k-1 non-zero D-classes, the R- and the L-preorder are complicated; in particular, <_R is dense (even within an L-class), and <_L is dense (even within an R-class). We study the computational complexity of the R- and the L-preorder. When inputs are given by words over a finite generating set of M_{k,1}, the R- and the L-preorder decision problems are in P. The main result of the paper is that over a "circuit-like" generating set, the R-preorder decision problem of M_{k,1} is Pi_2^P-complete, whereas the L-preorder decision problem is coNP-complete. We also prove related results about circuits: For combinational circuits, the surjectiveness problem is Pi_2^P-complete, whereas the injectiveness problem is coNP-complete.
Recommendations
- The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
- Monoid generalizations of the Richard Thompson groups.
- Bernoulli measure on strings, and Thompson-Higman monoids.
- FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
- The membership problem in aperiodic transformation monoids
Cites work
- A construction which can be used to produce finitely presented infinite simple groups
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
- Groups of piecewise linear homeomorphisms of the real line
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 47903 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1033441 (Why is no real title available?)
- scientific article; zbMATH DE number 774488 (Why is no real title available?)
- Monoid generalizations of the Richard Thompson groups.
- One-way permutations, computational asymmetry and distortion.
- The Chameleon groups of Richard J. Thompson: Automorphisms and dynamics
- THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
- The Ubiquity of Thompson's Group F in Groups of Piecewise Linear Homeomorphisms of the Unit Interval
Cited in
(12)- 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 Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
- On the circuit-size of inverses
- FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
- Polynomial-time right-ideal morphisms and congruences
- Semigroups and one-way functions
- A strong geometric hyperbolicity property for directed graphs and monoids.
- Monoids that map onto the Thompson-Higman groups
- Bernoulli measure on strings, and Thompson-Higman monoids.
- Monoid generalizations of the Richard Thompson groups.
This page was built for publication: The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580222)
