Cayley polynomial-time computable groups

DOI10.1016/J.IC.2021.104768MaRDI QIDQ2084772OpenAlexFDO

Authors D. A. Berdinskij, Murray Elder, 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)

Recommendations

• Cayley linear-time computable groups
• From automatic structures to automatic groups.
• C-graph automatic groups.
• Cayley automata
• Polynomial-time word problems.

Cites work

• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3257446 (Why is no real title available?)
• Algorithms and topology of Cayley graphs for groups.
• Automatic functions, linear time and learning
• BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
• Cayley automatic representations of wreath products
• Finite automata presentable Abelian groups
• Finitely generated semiautomatic groups
• Formal language theory and the geometry of 3-manifolds
• From automatic structures to automatic groups.
• Higher rank lamplighter groups are graph automatic
• Measuring closeness between Cayley automatic groups and automatic groups
• Metric properties of Baumslag-Solitar groups.
• Multi-stack-counter languages
• On a problem of Philip Hall
• On automatic transitive graphs
• On the geometry of Cayley automatic groups
• Parallel poly-pushdown groups
• Thompson's group \(F\) is 1-counter graph automatic.
• Towards quantitative classification of Cayley automatic groups
• \(\mathcal C\)-graph automatic groups.

Cited in

(5)

• Cayley Polynomial-Time Computable Groups
• scientific article; zbMATH DE number 3964134 (Why is no real title available?)
• Cayley linear-time computable groups
• Special issue: Selected papers of the 14th international conference on language and automata theory and applications, LATA 2020
• scientific article; zbMATH DE number 4057755 (Why is no real title available?)

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

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