Lamplighter groups and automata

DOI10.1007/S00236-022-00423-3OpenAlexW4293078754MaRDI QIDQ2170284FDOQ2170284

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

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (10)

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

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)