Transitive closure and related semiring properties via eliminants, Theoret

Closed semirings are algebraic structures that provide a unified approach to a number of seemingly unrelated problems of computer science and operations research. For example, semirings can be used to describe the algebra related to regular expressions, graph-theoretical path problems, and linear equa-tions. We present a new axiomatic formulation of semirings. We introduce the concept of eliminant, which simplifies the treatment of closed semirings considerably and yields very simple proofs of other-wise difficult theorems. We use eliminants to define matrix closure, formulate closure algorithms, and prove their correctness. Key words *-semirings, eliminants, asterates, transitive closure, iterative systems, linear systems.