Tree-based language complexity of Thompson's group F.
From MaRDI portal
Publication:889983
DOI10.1515/GCC-2015-0009zbMATH Open1335.20044arXiv1501.04315OpenAlexW2962859996MaRDI QIDQ889983FDOQ889983
Jennifer Taback, Sharif Younes
Publication date: 9 November 2015
Published in: Groups - Complexity - Cryptology (Search for Journal in Brave)
Abstract: The definition of graph automatic groups by Kharlampovich, Khoussainov and Miasnikov and its extension to C-graph automatic by Murray Elder and the first author raise the question of whether Thompson's group F is graph automatic. We define a language of normal forms based on the combinatorial "caret types" which arise when elements of F are considered as pairs of finite rooted binary trees, which we show to be accepted by a finite state machine with 2 counters, and forms the basis of a 3-counter graph automatic structure for the group.
Full work available at URL: https://arxiv.org/abs/1501.04315
Recommendations
- scientific article; zbMATH DE number 3854452
- On finite decomposition complexity of Thompson group.
- The counting complexity of group-definable languages
- Complexity among the finitely generated subgroups of Thompson's group
- Complexity, combinatorial group theory and the language of palutators
- On the topological complexity of tree languages
- Computing word length in alternate presentations of Thompson's group \(F\).
- A computational approach to the Thompson group F
- On subgroups of finite complexity in groups acting on trees.
- Context-free groups and their structure trees.
Formal languages and automata (68Q45) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Cited In (3)
This page was built for publication: Tree-based language complexity of Thompson's group \(F\).
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q889983)
