Thompson's group F is 1-counter graph automatic.

DOI10.1515/GCC-2016-0001zbMATH Open1344.20043arXiv1501.04313OpenAlexW2964148829MaRDI QIDQ285894FDOQ285894

Authors: Jennifer Taback, Murray Elder 

Publication date: 19 May 2016

Published in: Groups - Complexity - Cryptology (Search for Journal in Brave)

Abstract: It is not known whether Thompson's group F is automatic. With the recent extensions of the notion of an automatic group to graph automatic by Kharlampovich, Khoussainov and Miasnikov and then to C-graph automatic by the authors, a compelling question is whether F is graph automatic or C-graph automatic for an appropriate language class C. The extended definitions allow the use of a symbol alphabet for the normal form language, replacing the dependence on generating set. In this paper we construct a 1-counter graph automatic structure for F based on the standard infinite normal form for group elements.

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

Recommendations

• Some graphs related to Thompson's group \(F\).
• Autostackability of Thompson's group \(F\)
• Thompson's conjecture for some finite simple groups with connected prime graph.
• Combinatorial properties of Thompson’s group 𝐹
• Thompson's group F$F$ is almost 32$\frac{3}{2}$‐generated
• Thompson's conjecture for simple groups with connected prime graph.
• The automorphism group of Thompson's group \(F\): subgroups and metric properties.
• The Thompson chain of subgroups of the Conway group \(\mathrm{Co}_1\) and complete graphs on \(n\) vertices
• An abstract characterization of Thompson's group \(F\).
• The graph structure of graph groups that are subgroups of Thompson's group \(V\)

zbMATH Keywords

\(\mathcal C\)-graph automatic groupsgraph automatic groupsThompson group \(F\)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites Work

• Introductory notes on Richard Thompson's groups
• Title not available (Why is that?)
• Remarks on blind and partially blind one-way multicounter machines
• Quasi-isometrically embedded subgroups of Thompson's group \(F\)
• From automatic structures to automatic groups.
• On automatic transitive graphs
• Thompson’s Group and Public Key Cryptography
• \(\mathcal C\)-graph automatic groups.
• Title not available (Why is that?)
• A context-free and a 1-counter geodesic language for a Baumslag-Solitar group
• Title not available (Why is that?)
• Tame combing and almost convexity conditions.
• An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
• Tree-based language complexity of Thompson's group \(F\).

Cited In (5)

• \(\mathcal C\)-graph automatic groups.
• Cayley linear-time computable groups
• Autostackability of Thompson's group \(F\)
• Higher rank lamplighter groups are graph automatic
• Cayley polynomial-time computable groups

This page was built for publication: Thompson's group \(F\) is 1-counter graph automatic.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q285894)