Identities of triangular Boolean matrices

Abstract

We give a combinatorial characterization of the identities holding in the semiring of all upper triangular Boolean $n\times n$-matrices and apply the characterization to computational complexity of identity checking, finite axiomatizability of equational theories, and algebraic descriptions of certain classes of recognizable languages.

23 pages. In version 3, the proof of the main result is reorganized, two new corollaries are added, and Propositions 3.3 and 3.9 are provided with detailed proofs. In version 4, Example 2.4 is added