Commutative Doubly-Idempotent Semirings Determined by Chains and by Preorder Forests
| Autor: | Peter Jipsen, Natanael Alpay |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Relational and Algebraic Methods in Computer Science ISBN: 9783030435196 RAMiCS |
| DOI: | 10.1007/978-3-030-43520-2_1 |
| Popis: | 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 Langer 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\). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|