Alexander Gurney

Pathfinding through congruences

Citation Alexander J. T. Gurney and Timothy G. Griffin. 2011. Pathfinding through congruences. Proceedings of the 12th International Conference on Relational and Algebraic Methods in Computer Science (RAMICS 2011), Rotterdam. Springer LNCS 6663, p180-195.
Abstract Congruences of path algebras are useful in the definition and analysis of pathfinding problems, since properties of an algebra can be related to properties of its quotient. We show that this relationship can apply even when the algebraic objects involved satisfy weaker forms of the semiring or path algebra axioms. This is useful, since it is just these algebras and their quotients which we need to analyze pathfinding problems characterized by the need to obtain multiple paths even when path preferences are inconsistent, and paths can be filtered out arbitrarily, as in Internet routing.
Paper
PDF (161k)
Slides
PDF (460k)