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

Schreier graphintermediate growthautomatic structureautomatic graphCayley automatic group

Mathematics Subject Classification ID

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

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

• 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?)
• 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.
• 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
• C-graph automatic groups.
• \(\omega\)-periodic graphs

Cited in

(8)

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

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)