The finite basis problem for 2× 2 triangular Boolean matrix semirings and incidence semirings

@misc{jiao2026finite,
  title = {{The finite basis problem for $2\times 2$ triangular Boolean matrix semirings and incidence semirings}},
  author = {Jun Jiao and Xiaolei Shao},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.32356},
  eprint = {2609.32356},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.32356},
}

TY  - UNPB
TI  - The finite basis problem for 2× 2 triangular Boolean matrix semirings and incidence semirings
AU  - Jun Jiao
AU  - Xiaolei Shao
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.32356
UR  - https://arxiv.org/abs/2609.32356
AB  - An explicit finite identity basis is given for the eight-element semiring of upper triangular Boolean 2×2 matrices in the signature (+,·). The basis consists of a known multiplicative basis, the ai-semiring laws, and 30 mixed identities, each using at most eight variables. The proof combines a finite basis for the multiplicative reduct with finite rules for shuffling words, duplicating a marked occurrence, and interchanging adjacent occurrences while adding prescribed witnesses. This converts the one-letter gap criterion into a derivation of every valid semiring identity. We also study the band subvariety, a distinguished 156-element interval of the subvariety lattice, congruences, flat members, and finite representations of free algebras. Every m-letter word has an equivalent subword of length at most m^2 for m≥2, and the free algebras have doubly exponential rank growth. For arbitrary partially ordered sets, we determine the equational theory of Boolean relation semirings and of finite-support incidence semirings over nontrivial bounded distributive lattices: finite height h gives the theory of T_h, while unbounded height gives precisely the identities of all additively idempotent semirings.
ER  -