\(\mathcal C\)-graph automatic groups.

DOI10.1016/J.JALGEBRA.2014.04.021zbMath1334.20032arXiv1312.7425OpenAlexW1573311823MaRDI QIDQ403809

Jennifer Taback, Murray J. 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 problemBaumslag-Solitar groupspolynomial time algorithmsThompson 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)

Related Items (12)

Thompson's group \(F\) is 1-counter graph automatic. ⋮ On the geometry of Cayley automatic groups ⋮ Lamplighter groups and automata ⋮ Metric properties of Baumslag–Solitar groups ⋮ Higher rank lamplighter groups are graph automatic ⋮ Quasi-automatic semigroups ⋮ Cayley linear-time computable groups ⋮ Extending the synchronous fellow traveler property ⋮ Cayley Automatic Representations of Wreath Products ⋮ Cayley polynomial-time computable groups ⋮ BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS ⋮ An example of an automatic graph of intermediate growth

Cites Work

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

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