We consider semigroup algorithmic problems in the wreath product $\mathbb{Z} \wr \mathbb{Z}$. Our paper focuses on two decision problems introduced by Choffrut and Karhum\"{a}ki (2005): the Identity Problem (does a semigroup contain the neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of $\mathbb{Z} \wr \mathbb{Z}$. We show that both problems are decidable. Our result complements the undecidability of the Semigroup Membership Problem (does a semigroup contain a given element?) in $\mathbb{Z} \wr \mathbb{Z}$ shown by Lohrey, Steinberg and Zetzsche (ICALP 2013), and contributes an important step towards solving semigroup algorithmic problems in general metabelian groups.


翻译:我们考虑 $\mathbb{Z} \wr \mathbb{Z}$ 中复合半群的算法问题。本文着重探讨由 Choffrut 和 Karhum\"{a}ki (2005) 提出的两个决策问题:同一性问题(一个半群是否包含中性元素?)和群问题(一个半群是否为群?)因为 $\mathbb{Z} \wr \mathbb{Z}$ 中生成的子半群,我们表明这两个问题是可决定的。我们的结果补充了 Lohrey,Steinberg 和 Zetzsche (ICALP 2013) 显示的 $\mathbb{Z} \wr \mathbb{Z}$ 中复合半群成员问题(半群是否包含给定元素?)的不可判定性问题,并为解决不规则交换群中的半群算法问题迈出重要一步。

0
下载
关闭预览

相关内容

【ICDM2022教程】多目标优化与推荐,173页ppt
专知会员服务
41+阅读 · 2022年12月24日
Meta最新WWW2022《联邦计算导论》教程,附77页ppt
专知会员服务
59+阅读 · 2022年5月5日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
100+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
GitChat 超级会员 5 折,仅 2 天
人工智能头条
22+阅读 · 2018年12月28日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
Prompting with Pseudo-Code Instructions
Arxiv
0+阅读 · 2023年5月19日
Arxiv
0+阅读 · 2023年5月18日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
GitChat 超级会员 5 折,仅 2 天
人工智能头条
22+阅读 · 2018年12月28日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
Top
微信扫码咨询专知VIP会员