项重写系统和自由幺半群  

Term rewriting systems and free monoids

作　　者：林沐辰 朱志成 张毅 Lin Muchen;Zhu Zhicheng;Zhang Yi(School of Mathematics and Statistics,Nanjing University of Information Science and Technology,Nanjing 210044,China;School of Mathematics and Statistics,Lanzhou University,Lanzhou 730000,China)

机构地区：[1]南京信息工程大学数学与统计学院,江苏南京210044 [2]兰州大学数学与统计学院,甘肃兰州730000

出　　处：《纯粹数学与应用数学》2022年第2期266-275,共10页Pure and Applied Mathematics

基　　金：国家自然科学基金(11771191,12101316);南京信息工程大学人才启动金(2021r014);南京信息工程大学大学生创新创业训练计划项目(XJDC202210300386).

摘　　要：项重写系统起源于数理逻辑,是理论计算机科学的重要组成部分.关于项重写系统的一个主要问题是描述一个重写系统是否具有汇合或终止等基本性质.本文首先将一个项重写系统与自由幺半群上的二元关系联系起来.然后,基于自由幺半群上的项重写系统,刻画了收敛项重写系统与自由幺半群的商截面之间的关系.作为应用,分别给出了由三个元素生成的Platic幺半群和中国幺半群的截面.The concept of term rewriting system originated from mathematical logic and is an impor-tant part of theoretical computer science.One of the main problems in term rewriting systems is to characterize whether a rewriting system that has a fundamental property like confluence or termina-tion.In this paper,we first associate a term rewriting system to a binary relation on the free monoid.Based on the term rewriting system on free monoids,we then characterize the relationship between convergent term rewriting systems and sections of quotients of free monoids.As applications,we give respectively sections of Plactic monoids generated by three elements and Chinese monoids.

关 键 词：自由幺半群 重写系统 Platic幺半群 中国幺半群 

分 类 号：O152.7[理学—数学]