On the finite basis problem for certain 2-limited words. (Q1940888): Difference between revisions

Let \(X\) be a countably infinite alphabet. By \(X^*\) is denoted the free monoid on the alphabet \(X\). Elements of \(X\) and \(X^*\) are referred to as letters and words, respectively. Let \(x\) be any letter and \(w\) any word. Then the content of \(w\), denoted by \(c(w)\), is the set of all letters occurring in \(w\); \(occ(x,w)\) is the number of occurrences of the letter \(x\) in \(w\); \(x\) is said to be \(n\)-occurring in \(w\) if \(occ(x,w)=n\), and they say that \(x\) is less than \(m\)-occurring in \(w\) if \(m>n\) and \(x\) is more than \(m\)-occurring in \(w\) if \(m<n\); in particular, a \(1\)-occurring letter is called a linear letter, while a more than \(1\)-occurring letter is called a non-linear letter; \(w\) is said to be \(n\)-limited if \(occ(x,w)\leq n\) for all letters \(x\in c(w)\); \(w\) is said to be linear if \(occ(x,w)=1\) for all \(x\in c(w)\). Let \(M\) be a monoid and \(id(M)\) be the set of all semigroup identities satisfied by \(M\). The monoid \(M\) is finitely based if there exists a finite subset \(\Sigma\) of \(id(M)\) such that every identity in \(id(M)\) follows from the identities in \(\Sigma\). Otherwise, it is said to be non-finitely based. A subset \(W\) of \(X^*\) is called a language over \(X\). For a finite language \(W\) 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\). A language \(W\) (resp., a word \(w\)) is said to be finitely based if the monoid \(S(W)\) (resp., \(S(\{w\})\)) is finitely based. Otherwise, \(W\) (resp., \(w\)) is said to be non-finitely based. The authors give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, they describe all finitely based \(2\)-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide whether or not a \(2\)-limited word in which there are exactly two non-linear letters is finitely based.