Cayley automatic groups and numerical characteristics of Turing transducers

DOI10.1007/978-3-662-53132-7_3MaRDI QIDQ2817373zbMATH OpenOpenAlexFDO

Authors D. A. Berdinskij

Publication date 30 August 2016

Published in Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

Cayley automatic groupsFølner functiongrowth functionrandom walkTuring transducers

Mathematics Subject Classification ID

Extensions, wreath products, and other compositions of groups (20E22) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65) Formal languages and automata (68Q45)

Abstract: This paper is devoted to the problem of finding characterizations for Cayley automatic groups. The concept of Cayley automatic groups was recently introduced by Kharlampovich, Khoussainov and Miasnikov. We address this problem by introducing three numerical characteristics of Turing transducers: growth functions, Folner functions and average length growth functions. These three numerical characteristics are the analogs of growth functions, Folner functions and drifts of simple random walks for Cayley graphs of groups. We study these numerical characteristics for Turing transducers obtained from automatic presentations of labeled directed graphs.

Recommendations

• Towards quantitative classification of Cayley automatic groups
• From automatic structures to automatic groups.
• On automatic transitive graphs
• Cayley automata
• Cayley graphs and automatic sequences

Cites work

• An example of an automatic graph of intermediate growth
• An example of the rate of growth for a random walk on a group
• Approach for incorporating narrow band nonuniformity into nongray analyis of radiative heat transfer in nonisothermal and nonhomogeneous gas fields
• Cayley automatic representations of wreath products
• Deterministic automata. Simulation, universality and minimality
• Finite nondeterministic automata: simulation and minimality
• From automatic structures to automatic groups.
• scientific article; zbMATH DE number 3875506 (Why is no real title available?)
• scientific article; zbMATH DE number 5605134 (Why is no real title available?)
• scientific article; zbMATH DE number 1330031 (Why is no real title available?)
• scientific article; zbMATH DE number 3194856 (Why is no real title available?)
• On automatic transitive graphs
• On isoperimetric profiles of finitely generated groups.
• On the asymptotics of drift
• Rational and transcendental growth series for the higher Heisenberg groups
• STACS 2005
• Three lectures on automatic structures

Cited in

(9)

• Measuring closeness between Cayley automatic groups and automatic groups
• A geometric approach to (semi)-groups defined by automata via dual transducers.
• On automatic transitive graphs
• TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS
• scientific article; zbMATH DE number 64152 (Why is no real title available?)
• Growth Functions and Automatic Groups
• On the geometry of Cayley automatic groups
• Group-walking automata
• Independent finite automata on Cayley graphs

This page was built for publication: Cayley automatic groups and numerical characteristics of Turing transducers

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