On the Finite Basis Problem for Certain 2-limited Words

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 i...

Full description

Saved in:
Bibliographic Details
Published in:Acta mathematica Sinica. English series 2013-03, Vol.29 (3), p.571-590
Main Authors: Li, Jian Rong, Zhang, Wen Ting, Luo, Yan Feng
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Alphabets
Language
Mathematical analysis
Mathematics
Mathematics and Statistics
Monoids
Nonlinearity
Quotients
Studies
三元素
充分条件
基础
字母
有限基
理想
自由幺半群
非线性
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1439-8516
1439-7617
DOI:10.1007/s10114-012-0193-1