Matrix and matricial iteration theories. I (Q2366691)

The paper investigates matrix theories which are simultaneously iteration theories. Such theories are proved to be determined by semirings \(S\) equipped with a star operation satisfying certain equational properties. Section 4 gives a concrete description of the initial matrix theory \(T_ 0\) as being the theory of all matrices over a semiring \(S_ 0\) that is a quotient of a Conway semiring. An extension theorem is provided, showing that if \(\text{Mat}_ S\) is a matrix iteration theory, then so is \(\text{Mat}_ R\), where \(R\) is the semiring of all power series over \(S\). These results are useful to find equational axioms for the semiring of regular sets with the Kleene star operation, and to program correctness logic for nondeterministic flowchart algorithms. The investigations continue with Part II (reviewed below).