An example of an automatic graph of intermediate growth

DOI10.1016/J.APAL.2015.05.005zbMATH Open1322.68125arXiv1312.3710OpenAlexW1508514148MaRDI QIDQ2352257FDOQ2352257

Dmytro Savchuk, Alexei Myasnikov

Publication date: 30 June 2015

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

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.

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Automata Presenting Structures: A Survey of the Finite String Case
• Title not available (Why is that?)
• The combinatorial structure of cocompact discrete hyperbolic groups
• From automatic structures to automatic groups.
• \(\mathcal C\)-graph automatic groups.
• Symbolic dynamics and self-similar groups
• Title not available (Why is that?)
• Formal language theory and the geometry of 3-manifolds
• Cayley Graph Automatic Groups Are Not Necessarily Cayley Graph Biautomatic
• \(\omega\)-periodic graphs
• On a family of Schreier graphs of intermediate growth associated with a self-similar group
• Combings of groups and the grammar of reparameterization.
• Title not available (Why is that?)
• Tame filling invariants for groups

Cited In (4)

• SOLENOIDAL MAPS, AUTOMATIC SEQUENCES, VAN DER PUT SERIES, AND MEALY AUTOMATA
• 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
• Endomorphisms of regular rooted trees induced by the action of polynomials on the ring ℤd of d-adic integers

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)