Regular Algebra Applied to Path-finding Problems

DOI10.1093/imamat/15.2.161zbMath0304.68082OpenAlexW2060072995WikidataQ56874026 ScholiaQ56874026MaRDI QIDQ4060428

Bernard A. Carré, Roland C. Backhouse

Publication date: 1975

Published in: IMA Journal of Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d527b0f8ebfb23123f7a9ee826ca5ce2858e46a1

Mathematics Subject Classification ID

Related Items (40)

Stone Relation Algebras ⋮ Algebraic program analysis ⋮ Functional correctness of C implementations of Dijkstra's, Kruskal's, and Prim's algorithms ⋮ Transitive closure and related semiring properties via eliminants ⋮ Dioïds and semirings: Links to fuzzy sets and other applications ⋮ Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm ⋮ A unified framework for disambiguating finite transductions ⋮ Components and acyclicity of graphs. An exercise in combining precision with concision ⋮ Efficient algorithms for solving systems of linear equations and path problems ⋮ Les éléments p-réguliers dans les dioides ⋮ Verifying the Correctness of Disjoint-Set Forests with Kleene Relation Algebras ⋮ The equational logic of fixed points ⋮ A calculational approach to mathematical induction ⋮ Left omega algebras and regular equations ⋮ Universal algorithms for solving the matrix Bellman equations over semirings ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ Hopscotch -- reaching the target hop by hop ⋮ Nonlinear matrix decompositions and an application to parallel processing ⋮ Dijkstra, Floyd and Warshall meet Kleene ⋮ Relational characterisations of paths ⋮ Temporal constraint networks ⋮ The parallel computation of minimum cost paths in graphs by stream contraction ⋮ Fixed-point calculus ⋮ Verifying minimum spanning tree algorithms with Stone relation algebras ⋮ Morphological perceptrons with competitive learning: lattice-theoretical framework and constructive learning algorithm ⋮ On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection ⋮ Algebraic structures for transitive closure ⋮ An algebraic framework for minimum spanning tree problems ⋮ The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields ⋮ Semirings and path spaces ⋮ Weighted automata computation of edit distances with consolidations and fragmentations ⋮ Fast and efficient solution of path algebra problems ⋮ A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion) ⋮ Universal numerical algorithms and their software implementation ⋮ Wolfram's class IV automata and a good Life ⋮ Transitivity of generalized fuzzy matrices ⋮ Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings ⋮ A comparison of gaussian and gauss-jordan elimination in regular algebra ⋮ Regular algebra applied to language problems ⋮ Abstract abstract reduction

This page was built for publication: Regular Algebra Applied to Path-finding Problems