C-graph automatic groups.

DOI10.1016/J.JALGEBRA.2014.04.021MaRDI QIDQ403809zbMATHOpenAlexFDO

Authors Jennifer Taback, Murray Elder

Publication date 29 August 2014

Published in Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

word problemThompson groupspolynomial time algorithmsBaumslag-Solitar groupsCayley graph automatic groupscontext-sensitive languagescounter languages

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)

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 $mathcalC$, we call the resulting groups $mathcalC$-graph automatic. We prove that the class of $mathcalC$-graph automatic groups is closed under change of generating set, direct and free product for certain classes $mathcalC$. 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 Thompson's groups $F,T$ and $V$.

Recommendations

• From automatic structures to automatic groups.
• An automata theoretic approach to the generalized word problem in graphs of groups.
• Thompson's group \(F\) is 1-counter graph automatic.
• Graph groups are biautomatic
• Tree-based language complexity of Thompson's group \(F\).

Cites work

• scientific article; zbMATH DE number 5155118 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS
• A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.
• Cayley graph automatic groups are not necessarily Cayley graph biautomatic
• Counter machines and counter languages
• Developments in Language Theory
• Formal Languages and Groups as Memory
• Formal language theory and the geometry of 3-manifolds
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• GROUPS WITH INDEXED CO-WORD PROBLEM
• Groups with poly-context-free word problem.
• Growth Series of Some Wreath Products
• Metric properties of Baumslag-Solitar groups.
• Multi-stack-counter languages
• Multitape AFA
• ON GROUPS AND COUNTER AUTOMATA
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• On groups that have normal forms computable in logspace.
• Parallel poly-pushdown groups
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Remarks on blind and partially blind one-way multicounter machines
• Remarks on the complexity of nondeterministic counter languages
• Some geodesic problems in groups
• Space complexity and word problems of groups
• THE OCCURRENCE PROBLEM FOR FREE PRODUCTS OF GROUPS
• The co-word problem for the Higman-Thompson group is context-free
• The word and geodesic problems in free solvable groups.
• Word Problems Solvable in Logspace
• Word problems recognisable by deterministic blind monoid automata

Cited in

(15)

• Metric properties of Baumslag-Solitar groups.
• Cayley polynomial-time computable groups
• Thompson's group \(F\) is 1-counter graph automatic.
• Higher rank lamplighter groups are graph automatic
• BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
• Cayley linear-time computable groups
• Extending the synchronous fellow traveler property
• On the geometry of Cayley automatic groups
• Lamplighter groups and automata
• Cayley automatic representations of wreath products
• TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS
• An example of an automatic graph of intermediate growth
• Quasi-automatic semigroups
• From automatic structures to automatic groups.
• AUTOMATIC STRUCTURES FOR FUNDAMENTAL GROUPOIDS OF GRAPHS OF GROUPS

This page was built for publication: \(\mathcal C\)-graph automatic groups.

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