We consider certain decision problems for the free model of the theory of Cartesian monoids. We introduce a model of computation based on the notion of a single stack one-way PDA due to Ginsburg, Greibach and Harrison. This model allows us to solve problems such as (1) Given a finite set B of elements and an element F, is F a product of members of B? (2) Is the submonoid generated by the finite set B infinite? for certain fragments of the free Cartesian monoid. These fragments include the submonoid of right invertible elements and so our results apply to the Thompson-Higman groups.
翻译：我们考虑对笛卡尔单体理论自由模型的某些决定问题。我们引入了一种基于因金斯堡、格里巴奇和哈里森而形成的单堆单向PDA概念的计算模型。这一模型使我们能够解决问题,例如:(1) 鉴于元素的一组有限B和元素F,F是B成员的产品吗?(2) 对于自由笛卡尔单体的某些碎片,限制B产生的子分子是否无限?这些碎片包括不可忽略的右元素的子分子,因此我们的结果适用于汤普森-希格曼集团。
相关内容
微信扫码咨询专知VIP会员