Tilings and submonoids of metabelian groups.

DOI10.1007/S00224-010-9264-9zbMATH Open1229.20025arXiv0903.0648OpenAlexW2004793105MaRDI QIDQ633769FDOQ633769

Markus Lohrey, Benjamin Steinberg

Publication date: 30 March 2011

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

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.

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

Recommendations

• The submonoid and rational subset membership problems for graph groups.
• Rational subsets and submonoids of wreath products.
• Rational subsets and submonoids of wreath products.
• The rational subset membership problem for groups: a survey
• On the rational subset problem for groups.

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)

Cites Work

• Title not available (Why is that?)
• Occurrence problem for free solvable groups
• Rational sets in commutative monoids
• Title not available (Why is that?)
• The undecidability of the domino problem
• The classical decision problem.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Submonoids and rational subsets of groups with infinitely many ends.
• The Algorithmic Theory of Finitely Generated Metabelian Groups
• Title not available (Why is that?)
• The submonoid and rational subset membership problems for graph groups.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the rational subset problem for groups.
• Relative cohomology of finite groups and polynomial growth
• Semidirect products of pseudovarieties from the universal algebraist's point of view
• Title not available (Why is that?)

Cited In (10)

• Two problems for solvable and nilpotent groups
• Knapsack problems in groups
• Rational subsets and submonoids of wreath products.
• Rational subsets of unitriangular 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
• 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)