Cayley polynomial-time computable groups

DOI10.1016/j.ic.2021.104768OpenAlexW3046981564MaRDI QIDQ2084772

Murray J. Elder, Dmitry Berdinsky, Prohrak Kruengthomya

Publication date: 13 October 2022

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

Cayley distance functionCayley polynomial-time computable groupCayley position-faithful linear-time computable groupposition-faithful one-tape Turing machine

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (1)

Special issue: Selected papers of the 14th international conference on language and automata theory and applications, LATA 2020

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Thompson's group \(F\) is 1-counter graph automatic.
• \(\mathcal C\)-graph automatic groups.
• Algorithms and topology of Cayley graphs for groups.
• Finite automata presentable Abelian groups
• Parallel poly-pushdown groups
• Formal language theory and the geometry of 3-manifolds
• Measuring closeness between Cayley automatic groups and automatic groups
• Higher rank lamplighter groups are graph automatic
• From automatic structures to automatic groups.
• On a problem of Philip Hall
• Cayley Automatic Representations of Wreath Products
• Automatic functions, linear time and learning
• On Automatic Transitive Graphs
• Metric properties of Baumslag–Solitar groups
• Finitely generated semiautomatic groups
• BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
• On the geometry of Cayley automatic groups
• Towards quantitative classification of Cayley automatic groups
• Multi-stack-counter languages

This page was built for publication: Cayley polynomial-time computable groups