An example of an automatic graph of intermediate growth

DOI10.1016/J.APAL.2015.05.005MaRDI QIDQ2352257zbMATH OpenOpenAlexFDO

Authors Dmytro Savchuk, Alexei Myasnikov

Publication date 30 June 2015

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

automatic graphautomatic structureCayley automatic groupintermediate growthSchreier graph

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65) Formal languages and automata (68Q45)

Abstract: We give an example of a 4-regular infinite automatic graph of intermediate growth. It is constructed as a Schreier graph of a certain group generated by 3-state automaton. The question was motivated by an open problem on the existence of Cayley automatic groups of intermediate growth.

Recommendations

• On a family of Schreier graphs of intermediate growth associated with a self-similar group
• An automata group of intermediate growth and exponential activity
• Two-state Mealy automata of intermediate growth over a two-letter alphabet
• On automatic transitive graphs
• Growth of Schreier graphs of automaton groups.

Cites work

• C-graph automatic groups.
• \(\omega\)-periodic graphs
• Automata Presenting Structures: A Survey of the Finite String Case
• Cayley graph automatic groups are not necessarily Cayley graph biautomatic
• Combings of groups and the grammar of reparameterization.
• Formal language theory and the geometry of 3-manifolds
• From automatic structures to automatic groups.
• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1221772 (Why is no real title available?)
• scientific article; zbMATH DE number 1499098 (Why is no real title available?)
• On a family of Schreier graphs of intermediate growth associated with a self-similar group
• Symbolic dynamics and self-similar groups
• Tame filling invariants for groups
• The combinatorial structure of cocompact discrete hyperbolic groups

Cited in

(10)

• Schreier graphs of actions of Thompson's group \(F\) on the unit interval and on the Cantor set
• Cayley automatic groups and numerical characteristics of Turing transducers
• Growth of action graphs of finite automata
• On a family of Schreier graphs of intermediate growth associated with a self-similar group
• Endomorphisms of regular rooted trees induced by the action of polynomials on the ring \(\mathbb{Z}_d\) of \(d\)-adic integers
• SOLENOIDAL MAPS, AUTOMATIC SEQUENCES, VAN DER PUT SERIES, AND MEALY AUTOMATA
• A subperiodic tree whose intermediate branching number is strictly less than the lower intermediate growth rate
• Liftable self-similar groups and scale groups
• Explicit generators for the stabilizers of rational points in Thompson's group F
• An automata group of intermediate growth and exponential activity

This page was built for publication: An example of an automatic graph of intermediate growth

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