On the Finite Basis Problem for Certain 2-limited Words  

作　　者：Jian Rong LI Wen Ting ZHANG Yan Feng LUO 

机构地区：[1]Department of Mathematics, Lanzhou University

出　　处：《Acta Mathematica Sinica,English Series》2013年第3期571-590,共20页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China (Grant No. 10971086);Mathematical Tianyuan Foundation of China (Grant No. 11126186);Natural Science Foundation of Gansu Province (Grant No.1107RJZA218);Fundamental Research Funds for Central Universities (Grant No. lzujbky-2012-12)

摘　　要：Let X＊ be a free monoid over an alphabet X and W be a finite language over X. Let S（W） be the Rees quotient X＊/I（W）, where I（W） is the ideal of X＊ consisting of all elements of X＊ that are not subwords of W. Then S（W） is a finite monoid with zero and is called the discrete syntactic monoid of W. W is called finitely based if the monoid S（W） is finitely based. In this paper, we give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, we describe all finitely based 2-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide that whether or not a 2-limited word in which there are exactly two non-linear letters is finitely based.Let X＊ be a free monoid over an alphabet X and W be a finite language over X. Let S（W） be the Rees quotient X＊/I（W）, where I（W） is the ideal of X＊ consisting of all elements of X＊ that are not subwords of W. Then S（W） is a finite monoid with zero and is called the discrete syntactic monoid of W. W is called finitely based if the monoid S（W） is finitely based. In this paper, we give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, we describe all finitely based 2-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide that whether or not a 2-limited word in which there are exactly two non-linear letters is finitely based.

关 键 词：Finite basis problem 2-limited words discrete syntactic monoid 

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