Lamplighter groups and automata

DOI10.1007/S00236-022-00423-3MaRDI QIDQ2170284zbMATH OpenOpenAlexFDO

Authors Sanjay Jain, Birzhan Moldagaliyev, Frank Stephan, Tien Dat Tran

Publication date 30 August 2022

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-022-00423-3

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• The lamplighter group \(\mathbb Z_3 \wr \mathbb Z\) generated by a bireversible automaton
• Cross-wired lamplighter groups and linearity of automata groups
• Bireversible automata generating lamplighter groups
• Higher rank lamplighter groups are graph automatic

Cites work

• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1303030 (Why is no real title available?)
• scientific article; zbMATH DE number 871245 (Why is no real title available?)
• Algorithms and topology of Cayley graphs for groups.
• Automata Presenting Structures: A Survey of the Finite String Case
• Automatic functions, linear time and learning
• Automatic groups: A guided tour
• Automatic structures: twenty years later
• BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
• Cayley automatic representations of wreath products
• Characterizing \(\text{TC}^{0}\) in terms of infinite groups
• Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy
• Describing Groups
• FA-presentable groups and rings
• Finite presentations of infinite structures: Automata and interpretations
• Finitely generated semiautomatic groups
• Formal language theory and the geometry of 3-manifolds
• From automatic structures to automatic groups.
• Higher rank lamplighter groups are graph automatic
• Knapsack problems for wreath products
• Nonstandard Cayley automatic representations for fundamental groups of torus bundles over the circle
• On Relations Defined by Generalized Finite Automata
• On groups that have normal forms computable in logspace.
• On the domino problem of the Baumslag-Solitar groups
• Parallel poly-pushdown groups
• Reversible space equals deterministic space
• STACS 2005
• Semiautomatic structures
• Some solvable automaton groups.
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
• The Diophantine problem in some metabelian groups
• The emptiness problem for intersections of regular languages
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum
• Three lectures on automatic structures
• Wreath products and finitely presented groups
• \(\mathcal C\)-graph automatic groups.

Cited in

(10)

• Lamplighters admit weakly aperiodic SFTs
• Bireversible automata generating lamplighter groups
• The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata
• Higher rank lamplighter groups are graph automatic
• Cayley linear-time computable groups
• Lamplighter groups, bireversible automata, and rational series over finite rings
• Lamplighter groups
• Cross-wired lamplighter groups and linearity of automata groups
• Lamplighters, metabelian groups, and horocyclic products
• The lamplighter group \(\mathbb Z_3 \wr \mathbb Z\) generated by a bireversible automaton

This page was built for publication: Lamplighter groups and automata

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