Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Commutative Doubly-Idempotent Semirings Determined by Chains and by Preorder Forests
verfasst von : Natanael Alpay, Peter Jipsen
Erschienen in: Relational and Algebraic Methods in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A commutative doubly-idempotent semiring (cdi-semiring) \((S,\vee ,\cdot ,0,1)\) is a semilattice \((S,\vee ,0)\) with \(x\vee 0 =x\) and a semilattices \((S,\cdot ,1)\) with identity 1 such that \(x0=0\), and \(x(y\vee z)=xy \vee xz \) holds for all \(x,y,z\in S\). Bounded distributive lattices are cdi-semirings that satisfy \(xy=x\wedge y\), and the variety of cdi-semirings covers the variety of bounded distributive lattices. Chajda and Länger showed in 2017 that the variety of all cdi-semirings is generated by a 3-element cdi-semiring. We show that there are seven cdi-semirings with a \(\vee \)-semilattice of height less than or equal to 2. We construct all cdi-semirings for which their multiplicative semilattice is a chain with \(n+1\) elements, and we show that up to isomorphism the number of such algebras is the \(n^\text {th}\) Catalan number \(C_{n}=\frac{1}{n+1}{2n\atopwithdelims ()n}\). We also show that cdi-semirings with a complete atomic Boolean \(\vee \)-semilattice on the set of atoms A are determined by singleton-rooted preorder forests on the set A. From these results we obtain efficient algorithms to construct all multiplicatively linear cdi-semirings of size n and all Boolean cdi-semirings of size \(2^n\).