On the finite basis problem for certain 2-limited words.
type: Item
instance of: scholarly article
title: On the finite basis problem for certain 2-limited words.
zbMATH Open document ID: 1271.20068
author: Wen Ting Zhang
author: Jian Rong Li
author: Yanfeng Luo
publication date: 2013-03-08T00:00:00Z
review text: 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…
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 08B05
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6142998
zbMATH Keywords: free monoids
zbMATH Keywords: varieties of semigroups
zbMATH Keywords: semigroup identities
zbMATH Keywords: finite basis problem
zbMATH Keywords: 2-limited words
zbMATH Keywords: discrete syntactic monoids
reviewed by: Leonid M. Martynov
MaRDI profile type: Publication
full work available at URL: s10114-012-0193-1
OpenAlex ID: W2000601605
cites work: TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
cites work: On certain finitely based varieties of semigroups
cites work: Varieties generated by semigroups of order four
cites work: Finite semigroups whose varieties have uncountably many subvarieties
cites work: SUBVARIETIES OF THE VARIETY GENERATED BY THE FIVE-ELEMENT BRANDT SEMIGROUP
cites work: Identity bases for some non-exact varieties.
cites work: Bases for equational theories of semi-groups
cites work: FINITELY BASED WORDS
cites work: The finite basis problem for finite semigroups
cites work: The subvariety lattice of the join of two semigroup varieties.
cites work: Finitely based, finite sets of words
cites work: Q2754914
cites work: Q3765976
cites work: Q3934450
cites work: Q4846425
cites work: Finiteness properties of varieties and the restriction to finite algebras.
cites work: FINITE SEMIGROUPS WITH INFINITE IRREDUNDANT IDENTITY BASES
DOI: 10.1007/S10114-012-0193-1
published in: Acta Mathematica Sinica, English Series
description: scientific article; zbMATH DE number 6142998