Algebraic structures for transitive closure

DOI10.1016/0304-3975(77)90056-1zbMath0358.68061OpenAlexW2039829163MaRDI QIDQ1238415

Daniel J. Lehmann

Publication date: 1977

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

Full work available at URL: http://wrap.warwick.ac.uk/46308/7/WRAP_Lehmann_cs-rr-010.pdf

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Algorithms in computer science (68W99)

Related Items

An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs ⋮ Algebraic program analysis ⋮ Transitive closure and related semiring properties via eliminants ⋮ Periodic sets of integers ⋮ Idempotent and tropical mathematics; complexity of algorithms and interval analysis ⋮ Metabolic isotopomer labeling systems. III: Path tracing ⋮ Inductive semimodules and the vector modules over them. ⋮ A unified framework for disambiguating finite transductions ⋮ Polynomial Functors Constrained by Regular Expressions ⋮ Efficient algorithms for solving systems of linear equations and path problems ⋮ The equational logic of fixed points ⋮ Universal algorithms for solving the matrix Bellman equations over semirings ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ Unnamed Item ⋮ ALGORITHMS FOR THE JOIN AND AUTO-INTERSECTION OF MULTI-TAPE WEIGHTED FINITE-STATE MACHINES ⋮ Unnamed Item ⋮ ON THE COMPUTATION OF THE RELATIVE ENTROPY OF PROBABILISTIC AUTOMATA ⋮ Temporal constraint networks ⋮ Algebraic structures for transitive closure ⋮ Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization ⋮ kProbLog: An Algebraic Prolog for Kernel Programming ⋮ THE VALIDITY OF WEIGHTED AUTOMATA ⋮ A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion) ⋮ Universal numerical algorithms and their software implementation ⋮ Allowable processing orders in the accelerated cascade algorithm

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Algebraic structures for transitive closure
• Regular Algebra Applied to Path-finding Problems
• Global Data Flow Analysis and Iterative Algorithms
• A Note on a Generalization of Boolean Matrix Theory
• A Theorem on Boolean Matrices