The co-word problem for the Higman-Thompson group is context-free

DOI10.1112/BLMS/BDL043zbMath1166.20025OpenAlexW2077926207MaRDI QIDQ5297606

Jörg Lehnert, Pascal Schweitzer

Publication date: 12 July 2007

Published in: Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/blms/bdl043

zbMATH Keywords

finitely generated groupscontext-free languagespush-down automataHoughton groupsHigman-Thompson groupsco-word problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items (22)

Some embeddings between symmetric R. thompson groups ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Parallel algorithms for power circuits and the word problem of the Baumslag group ⋮ Groups of piecewise isometric permutations of lattice points, or Finitary rearrangements of tessellations ⋮ Normalish Amenable Subgroups of the R. Thompson Groups ⋮ Context-free pairs of groups. I: Context-free pairs and graphs ⋮ Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups ⋮ Rational embeddings of hyperbolic groups ⋮ Closure properties of knapsack semilinear groups ⋮ Monoid generalizations of the Richard Thompson groups. ⋮ CONTEXT-FREE GROUPS AND THEIR STRUCTURE TREES ⋮ Unnamed Item ⋮ A dynamical definition of f.g. virtually free groups ⋮ Knapsack in hyperbolic groups ⋮ The word problem of the Brin-Thompson group is \textsf{coNP}-complete ⋮ Groups whose word problems are not semilinear ⋮ Monoids that map onto the Thompson-Higman groups ⋮ Embeddings into Thompson's group V and coCF groups ⋮ Groups Whose Word Problem is a Petri Net Language ⋮ Free products in R. Thompson’s group 𝑉 ⋮ Regular left-orders on groups ⋮ Knapsack Problems for Wreath Products

Cites Work

• Unnamed Item
• Unnamed Item
• Groups, the theory of ends, and context-free languages
• The accessibility of finitely presented groups
• GROUPS WITH INDEXED CO-WORD PROBLEM
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• Finiteness properties of groups

This page was built for publication: The co-word problem for the Higman-Thompson group is context-free