Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user$mathcal C$-graph automatic groups
125
0
0.0
(
0
)
Added by
Murray Elder
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We generalize the notion of a graph automatic group introduced by Kharlampovich, Khoussainov and Miasnikov (arXiv:1107.3645) by replacing the regular languages in their definition with more powerful language classes. For a fixed language class $mathcal C$, we call the resulting groups $mathcal C$-graph automatic. We prove that the class of $mathcal C$-graph automatic groups is closed under change of generating set, direct and free product for certain classes $mathcal C$. We show that for quasi-realtime counter-graph automatic groups where normal forms have length that is linear in the geodesic length, there is an algorithm to compute normal forms (and therefore solve the word problem) in polynomial time. The class of quasi-realtime counter-graph automatic groups includes all Baumslag-Solitar groups, and the free group of countably infinite rank. Context-sensitive-graph automatic groups are shown to be a very large class, which encompasses, for example, groups with unsolvable conjugacy problem, the Grigorchuk group, and Thompsons groups $F,T$ and $V$.
rate research
Read More
It is not known whether Thompsons 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.
We show that the higher rank lamplighter groups, or Diestel-Leader groups $Gamma_d(q)$ for $d geq 3$, are graph automatic. This introduces a new family of graph automatic groups which are not automatic.
We consider the class of groups whose word problem is poly-context-free; that is, an intersection of finitely many context-free languages. We show that any group which is virtually a finitely generated subgroup of a direct product of free groups has poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some of the techniques introduced for proving languages not to be poly-context-free may be of independent interest.
We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), is an EDT0L language whose specification can be computed in NSPACE$(n^2log n)$ for the torsion-free case and NSPACE$(n^4log n)$ in the torsion case. Furthermore, in the presence of quasi-isometrically embeddable rational constraints, we show that the full set of solutions to systems of equations in a hyperbolic group remains EDT0L. Our work combines the geometric results of Rips, Sela, Dahmani and Guirardel on the decidability of the existential theory of hyperbolic groups with the work of computer scientists including Plandowski, Je.z, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.
We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: their Cayley graphs are geodetic and side-lengths of non-degenerate triangles are uniformly bounded. This leads to a new algebraic result: the group is plain (isomorphic to the free product of finitely many finite groups and copies of $mathbb Z$) if and only if a certain relation on the set of non-trivial finite-order elements of the group is transitive on a bounded set. We use this to prove that deciding if a group presented by an inverse-closed finite convergent length-reducing rewriting system is not plain is in $mathsf{NP}$. A yes answer would disprove a longstanding conjecture of Madlener and Otto from 1987. We also prove that the isomorphism problem for plain groups presented by inverse-closed finite convergent length-reducing rewriting systems is in $mathsf{PSPACE}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
