The Rational Subset Membership Problem for Groups: A Survey
The Rational Subset Membership Problem for Groups: A Survey
复制标题
群体的合理子集成员资格问题：一项调查
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Markus Lohrey
中科院分区：
文献类型：
--
作者：
Markus Lohrey
群G的有理子集类是包含G的所有有限子集且关于并、积和取由集合生成的么半群封闭的最小类。群G的有理子集成员问题是一个判定问题，其中对于给定的群G的有理子集和群元素g，询问g是否∈ G。本文综述了群的有理子集成员问题的可判定性和不可判定性结果。同时也讨论了群生成的子幺半群和群生成的子群的成员问题。
The class of rational subsets of a group G is the smallest class that contains all finite subsets of G and that is closed with respect to union, product and taking the monoid generated by a set. The rational subset membership problem for a finitely generated group G is the decision problem, where for a given rational subset of G and a group element g it is asked whether g ∈ G. This paper presents a survey on known decidability and undecidability results for the rational subset membership problem for groups. The membership problems for finitely generated submonoids and finitely generated subgroups will be discussed as well.