Lamplighter groups and automata

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Three Lectures on Automatic Structures
• Automata Presenting Structures: A Survey of the Finite String Case
• 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
• 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
• 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
• Knapsack Problems for Wreath Products

Cited In (2)

• Cayley linear-time computable groups
• Lamplighter groups, bireversible automata, and rational series over finite rings

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)