On automatic transitive graphs

DOI10.1007/978-3-319-09698-8_1MaRDI QIDQ2921970zbMATH OpenOpenAlexFDO

Authors D. A. Berdinskij, Bakhadyr Khoussainov

Publication date 14 October 2014

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

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

zbMATH Keywords

finite automatatransitive graphsautomatic graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extensions, wreath products, and other compositions of groups (20E22)

Abstract: We construct the representations of Cayley graphs of wreath products using finite automata, pushdown automata and nested stack automata. These representations are in accordance with the notion of Cayley automatic groups introduced by Kharlampovich, Khoussainov and Miasnikov and its extensions introduced by Elder and Taback. We obtain the upper and lower bounds for a length of an element of a wreath product in terms of the representations constructed.

Recommendations

• From automatic structures to automatic groups.
• On transitive Cayley graphs of strong semilattices of right (left) groups
• Cayley graph automatic groups are not necessarily Cayley graph biautomatic
• Cayley automatic groups and numerical characteristics of Turing transducers
• Cayley automatic representations of wreath products

Cited in

(15)

• Automatic proof of graph nonisomorphism
• Automatic graphs and D0L-sequences of finite graphs
• An example of an automatic graph of intermediate growth
• Thompson's group F is 1-counter graph automatic.
• Cayley graphs with few automorphisms: the case of infinite groups
• Cayley automatic groups and numerical characteristics of Turing transducers
• Cayley graph automatic groups are not necessarily Cayley graph biautomatic
• Finitely generated semiautomatic groups
• BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
• On the geometry of Cayley automatic groups
• From automatic structures to automatic groups.
• String compression in FA-presentable structures
• Higher rank lamplighter groups are graph automatic
• Cayley polynomial-time computable groups
• Some natural decision problems in automatic graphs

This page was built for publication: On automatic transitive graphs

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