论文部分内容阅读
本文主要研究一关系半群的自动性，完整刻画了关系长度小于或等于3的一关系半群的自动性.全文共两章. 第一章是相关的基本概念和预备知识.主要介绍关于幺半群、正则语言(regular language)、自动幺半群(automatic monoid)和双自动幺半群等概念和已知结果.由于Gr(o)bner-Shirshov基理论对寻求半群的自动结构(automaticstructure)很有帮助，我们也介绍结合代数上的Gr(o)bner-Shirshov基理论. 第二章讨论长度小于或等于3的一关系的半群的自动性.我们利用Gr(o)bner-Shirshov基的相关技巧选取半群的规范型(normal form)，设法构造其自动结构.主要结果（定理2.2.6)如下:设S=sgp，A={a1，a2，…，an}，n∈N，u，v∈A*，|v|≤|u|≤3，其中A*是由A生成的自由幺半群.则S是一个自动半群当且仅当u=v(∈){aba=ba，aab=ba，abb=bb|a，b∈A，a≠b}.