Tilings and submonoids of metabelian groups.

DOI10.1007/S00224-010-9264-9MaRDI QIDQ633769zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Benjamin Steinberg

Publication date 30 March 2011

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

tilingsTuring machinesfinitely generated metabelian groupsrational subsetssubmonoid membership problemgeneralized word problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Extensions, wreath products, and other compositions of groups (20E22) Generators, relations, and presentations of groups (20F05) Cancellation theory of groups; application of van Kampen diagrams (20F06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Solvable groups, supersolvable groups (20F16) Free semigroups, generators and relations, word problems (20M05) Turing machines and related notions (03D10)

Abstract: In this paper we show that membership in finitely generated submonoids is undecidable for the free metabelian group of rank 2 and for the wreath product $mathbbZwr(mathbbZimesmathbbZ)$. We also show that subsemimodule membership is undecidable for finite rank free $(mathbbZimesmathbbZ)$-modules. The proof involves an encoding of Turing machines via tilings. We also show that rational subset membership is undecidable for two-dimensional lamplighter groups.

Recommendations

• The submonoid and rational subset membership problems for graph groups.
• The rational subset membership problem for groups: a survey
• On the rational subset problem for groups.

Cites work

• scientific article; zbMATH DE number 3652593 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3504469 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• scientific article; zbMATH DE number 1985667 (Why is no real title available?)
• scientific article; zbMATH DE number 848082 (Why is no real title available?)
• scientific article; zbMATH DE number 3339488 (Why is no real title available?)
• scientific article; zbMATH DE number 2209675 (Why is no real title available?)
• Occurrence problem for free solvable groups
• On the rational subset problem for groups.
• Rational sets in commutative monoids
• Relative cohomology of finite groups and polynomial growth
• Semidirect products of pseudovarieties from the universal algebraist's point of view
• Submonoids and rational subsets of groups with infinitely many ends.
• The Algorithmic Theory of Finitely Generated Metabelian Groups
• The classical decision problem.
• The submonoid and rational subset membership problems for graph groups.
• The undecidability of the domino problem

Cited in

(10)

• Two problems for solvable and nilpotent groups
• Knapsack problems in groups
• Undecidability of the submonoid membership problem for free nilpotent group of class $l\geqslant 2$ of sufficiently large rank
• The submonoid and rational subset membership problems for graph groups.
• Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two
• Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups
• Rational subsets of unitriangular groups.
• Simulations and the lamplighter group
• Submonoids and rational subsets of groups with infinitely many ends.
• A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module

This page was built for publication: Tilings and submonoids of metabelian groups.

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