Regular Algebra Applied to Path-finding Problems

DOI10.1093/IMAMAT/15.2.161MaRDI QIDQ4060428zbMATH OpenOpenAlexWikidataFDO

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)

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

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)