FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY

DOI10.1142/S0218196708004457zbMath1186.68203arXivmath/0607349OpenAlexW2029769851WikidataQ114072952 ScholiaQ114072952MaRDI QIDQ3520362

Jean-Camille Birget

Publication date: 26 August 2008

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

complexityword problemcircuitscoNP-completenessThompson-Higman groupsinfinite generating setslength preserving elements

Mathematics Subject Classification ID

Related Items (6)

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. ⋮ One-way permutations, computational asymmetry and distortion. ⋮ THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID M_{k, 1} AND THEIR COMPLEXITY ⋮ The word problem of the Brin-Thompson group is \textsf{coNP}-complete ⋮ Bernoulli measure on strings, and Thompson-Higman monoids.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
• A construction which can be used to produce finitely presented infinite simple groups
• Groups of piecewise linear homeomorphisms of the real line
• Sur un groupe remarquable de difféomorphismes du cercle. (On a remarkable group of the diffeomorphisms of the circle)
• Conservative logic
• The Chameleon groups of Richard J. Thompson: Automorphisms and dynamics
• Geometric presentations for Thompson's groups.
• Parallel Prefix Computation
• The Ubiquity of Thompson's Group F in Groups of Piecewise Linear Homeomorphisms of the Unit Interval
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• ON THE ZAPPA-SZÉP PRODUCT
• Combinatorial properties of Thompson’s group 𝐹
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• THE ALGEBRA OF STRAND SPLITTING II: A PRESENTATION FOR THE BRAID GROUP ON ONE STRAND

This page was built for publication: FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY