On the lattice of sub-pseudovarieties of DA.

DOI10.1007/S00233-010-9258-6MaRDI QIDQ711615zbMATH OpenOpenAlexFDO

Authors Manfred Kufleitner, Pascal Weil

Publication date 27 October 2010

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.2893

zbMATH Keywords

bases of pseudoidentitiescomplete lattice homomorphismslattices of band varietieslattices of pseudovarietiesMalcev productspseudovarieties of finite semigroupsvarieties of languages

Mathematics Subject Classification ID

Lattices of varieties (08B15) Quasivarieties (08C15) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: The wealth of information that is available on the lattice of varieties of bands, is used to illuminate the structure of the lattice of sub-pseudovarieties of DA, a natural generalization of bands which plays an important role in language theory and in logic. The main result describes a hierarchy of decidable sub-pseudovarieties of DA in terms of iterated Mal'cev products with the pseudovarieties of definite and reverse definite semigroups.

Review text

Let \(\mathbf{SL}\), \(\mathbf{LZ}\), \(\mathbf{RZ}\), \(\mathbf B\), \(\mathbf{DA}\), and \(\mathbf K\), \(\mathbf D\) denote the pseudovarieties of finite semigroups consisting, respectively, of all semilattices, all left/right-zero semigroups, all bands, all semigroups in which all regular elements are idempotents, and all semigroups in which idempotents are left/right zeros. The paper brings new insight into the lattice of subpseudovarieties of \(\mathbf{DA}\) by describing a hierarchy of decidable subpseudovarieties. It builds on earlier work of \textit{N. R. Reilly} and \textit{S. Zhang} [Bull.\ Aust.\ Math.\ Soc.\ 55, No.\ 2, 207-218 (1997; Zbl 0881.20027)], who showed that the correspondence \(\mathbf V\mapsto\mathbf V\cap\mathbf B\) is a complete lattice homomorphism, and of \textit{P. Trotter} and \textit{P. Weil} [Algebra Univers.\ 37, No.\ 4, 491-526 (1997; Zbl 0906.20036)], who independently proved that the restriction of that mapping to the lattice of subpseudovarieties of \(\mathbf{DA}\) is a complete lattice homomorphism and described, by means of finite bases of pseudoidentities, for each band pseudovariety \(\mathbf Y\), the largest subpseudovariety \(\mathbf Y^\uparrow\) of \(\mathbf{DA}\) such that \(\mathbf Y^\uparrow\cap\mathbf B=\mathbf Y\). In the present paper, it is shown that the nontrivial monoidal meet irreducible pseudovarieties of the form \(\mathbf Y^\uparrow\) can be obtained from \(\mathbf{SL}\) by alternately applying the operators \(\mathbf K\circm-\) and \(\mathbf D\circm-\), where \(\circm\) denotes the Mal'cev product of pseudovarieties. This result has a natural interpretation in terms of varieties of languages.

Recommendations

• The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue
• Some pseudovariety joins involving the pseudovariety of finite groups
• On a problem of Brzozowski and Fich
• The lattices of varieties and pseudovarieties of band monoids
• Varieties and pseudovarieties generated by D-chains
• Pseudovarieties of completely regular semigroups
• On maximal pseudo-varieties of finite monoids and semigroups
• Join irreducible semigroups
• Varieties of idempotent semirings with commutative addition.
• Complete endomorphisms of the lattice of pseudovarieties of finite semigroups

Cites work

• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• All Varieties of Bands I
• Complete endomorphisms of the lattice of pseudovarieties of finite semigroups
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3640907 (Why is no real title available?)
• scientific article; zbMATH DE number 1944133 (Why is no real title available?)
• scientific article; zbMATH DE number 1775408 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 798167 (Why is no real title available?)
• Logic Meets Algebra: the Case of Regular Languages
• On FO 2 Quantifier Alternation over Words
• On radical congruence systems
• PROFINITE METHODS IN SEMIGROUP THEORY
• Profinite semigroups, Mal'cev products, and identities
• Some results on the dot-depth hierarchy
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• Sur le produit de concatenation non ambigu
• The lattice of equational classes of idempotent semigroups
• The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue
• The lattices of varieties and pseudovarieties of band monoids
• Varieties of Bands Revisited

Cited in

(10)

• The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue
• The word problem for omega-terms over the Trotter-Weil hierarchy
• Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands
• The lattices of pseudovarieties of DA and B
• On FO 2 Quantifier Alternation over Words
• THE GLOBALS OF SOME SUBPSEUDOVARIETIES OF $\mathsf{DA}$
• A SYNTACTICAL PROOF OF LOCALITY OF DA
• SOME OPERATORS THAT PRESERVE THE LOCALITY OF A PSEUDOVARIETY OF SEMIGROUPS
• The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
• The amazing mixed polynomial closure and its applications to two-variable first-order logic

This page was built for publication: On the lattice of sub-pseudovarieties of DA.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q711615)