Regular Algebra Applied to Path-finding Problems

DOI10.1093/IMAMAT/15.2.161zbMATH Open0304.68082OpenAlexW2060072995WikidataQ56874026 ScholiaQ56874026MaRDI QIDQ4060428FDOQ4060428

Authors: 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

Formal languages and automata (68Q45) Deterministic network models in operations research (90B10) Algebraic systems of matrices (15A30)

Cited In (41)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4060428)