Transitive closure and related semiring properties via eliminants

DOI10.1016/0304-3975(85)90170-7zbMath0618.16036OpenAlexW2098410044MaRDI QIDQ1089083

B. David Saunders, S. Kamal Abdali

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90170-7

zbMATH Keywords

algorithmssolutionsmatrix equationssystems of equationseliminantsGauss-Jordan elimination methodmatrices over semiringssemiring of matrices

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Endomorphism rings; matrix rings (16S50) Graph theory (including graph drawing) in computer science (68R10) Matrix equations and identities (15A24) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Semirings (16Y60) Linear equations (linear algebraic aspects) (15A06)

Related Items

Dioïds and semirings: Links to fuzzy sets and other applications, A unified framework for disambiguating finite transductions, Filter-embedding semiring fusion for programming with MapReduce, Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization, Computing transitive closure on systolic arrays of fixed size

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic structures for transitive closure
• Shortest-path algorithms: Taxonomy and annotation
• Regular Algebra Applied to Path-finding Problems
• Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree, and Related Circuit Routing Problems (1956–1974)
• Global Data Flow Analysis and Iterative Algorithms
• Généralisation de l'algorithme de Warshall
• A Note on a Generalization of Boolean Matrix Theory
• A Theorem on Boolean Matrices