Hopscotch - reaching the target hop by hop

Peter Höfner*, Annabelle McIver

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Abstract Concrete and abstract relation algebras have widespread applications in computer science. One of the most famous is graph theory. Classical relations, however, only reason about connectivity, not about the length of a path between nodes. Generalisations of relation algebra, such as the min-plus algebra, use numbers allowing the treatment of weighted graphs. In this way one can for example determine the length of shortest paths (e.g. Dijkstra's algorithm). In this paper we treat matrices that carry even more information, such as the "next hop" on a path towards a destination. In this way we can use algebra not only for determining the length of paths, but also the concrete path. We show how paths can be reconstructed from these matrices, hop by hop. We further sketch an application for message passing in wireless networks.

Original languageEnglish
Article number397
Pages (from-to)212-224
Number of pages13
JournalJournal of Logical and Algebraic Methods in Programming
Issue number2
Publication statusPublished - Mar 2014


  • Kleene algebra
  • Path algebra
  • Routing
  • Semiring


Dive into the research topics of 'Hopscotch - reaching the target hop by hop'. Together they form a unique fingerprint.

Cite this