Transitive closure and related semiring properties via eliminants
type: Item
instance of: scholarly article
title: Transitive closure and related semiring properties via eliminants
zbMATH Open document ID: 0618.16036
DOI: 10.1016/0304-3975(85)90170-7
author: S. Kamal Abdali
author: B. David Saunders
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: Let \((S,+,\cdot)\) be a semiring such that \((S,+)\) is a commutative semigroup with neutral 0 and (S,\(\cdot)\) is a semigroup with neutral e, and assume (1) \(0a=a0=0\) for all \(a\in S\). Semirings of this kind, mostly those with idempotent addition, have become valuable tools, e.g. for various ''path problems'', in the theory of languages and in data flow analysis. In this context, solutions of the equations (2) \(x=ax+e=xa+e\) in S and (3) \(X=AX+E=XA+E\) in the semiring \(M_ n(S)\) of \(n\times n\)- matrices over S are of importance, and the literature deals with numerous methods to obtain a (suitable) solution of (3) for some \(A\in M_ n(S)\), mostly by the aid of solutions of (2) for several elements \(a\in S\). In particular, each equation (3) is solvable iff each equation (2) is, but uniqueness of the latter does not imply uniqueness of the former [cf. e.g. \textit{B. Mahr}, Ann. Discrete Math. 19, 229-256 (1984; Zbl 0567.16025) and references given there]. The paper deals only with semirings S such that each equation (2) has solutions and denotes one of them by \(a^*\). Depending on that choice, the ''eliminant'' \(| A|\) of a matrix \(A\in M_ n(S)\) is defined and a corresponding theory developed, which has some resemblance to the linear algebraic concept of determinants. By the aid of these eliminants, for each \(A\in M_ n(S)\) a matrix \(A^*\) is defined which is a solution of (3). Three algorithms - clearly depending on \(a^*\) in S - are given and shown to produce \(A^*\), e.g. that of McNaughton and Yamada which is similar to the Gauss-Jordan elimination method for inverting matrices in linear algebra. Moreover, for systems of equations \(x_{\nu}=a_{\nu 1}x_ 1+...+a_{\nu n}x_ n+b_{\nu}\) in S one solution \((x_ 1,...,x_ n)\) is directly given by one eliminant for each \(x_{\nu}\), and similarly for an equation \(X=XA+B\) in \(M_ n(S).\) Important remark: It is claimed that all this can be applied to a semiring S obtained from the field \(({\mathbb{…
Mathematics Subject Classification ID: 16Y60
Mathematics Subject Classification ID: 16S50
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15A06
Mathematics Subject Classification ID: 15A24
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4002328
zbMATH Keywords: matrices over semirings
zbMATH Keywords: matrix equations
zbMATH Keywords: semiring of matrices
zbMATH Keywords: solutions
zbMATH Keywords: eliminants
zbMATH Keywords: algorithms
zbMATH Keywords: Gauss-Jordan elimination method
zbMATH Keywords: systems of equations
reviewed by: Hanns Joachim Weinert
describes a project that uses: Algorithm 97
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90170-7
OpenAlex ID: W2098410044
cites work: Q4065051
cites work: Regular Algebra Applied to Path-finding Problems
cites work: Q3903001
cites work: Q5639639
cites work: Shortest-path algorithms: Taxonomy and annotation
cites work: Q5514188
cites work: Q4091732
cites work: Global Data Flow Analysis and Iterative Algorithms
cites work: Algebraic structures for transitive closure
cites work: Q5536277
cites work: Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree, and Related Circuit Routing Problems (1956–1974)
cites work: Généralisation de l'algorithme de Warshall
cites work: A Theorem on Boolean Matrices
cites work: A Note on a Generalization of Boolean Matrix Theory
Recommended article: Q3572784
Recommended article: Q3358736
Recommended article: On certain closure operators defined by families of semiring morphisms
Recommended article: Transitive closure for restricted classes of partial orders
Recommended article: On the existence and construction of \(T\)-transitive closures.
Recommended article: Closure Theorem for Partially Semialgebraic Sets
Recommended article: On the semigroup of closure operations
Recommended article: Closure under transfinite extensions
Recommended article: Q3602774
Recommended article: On the power of deterministic transitive closures
description: scientific article; zbMATH DE number 4002328