The Constrained Shortest Path Problem: A Case Study in Using ASMs
| dc.creator | Strötmann,Karl | |
| dc.date | 1997 | |
| dc.date.accessioned | 2024-02-06T12:48:46Z | |
| dc.date.available | 2024-02-06T12:48:46Z | |
| dc.description | This paper addresses the correctness problem of an algorithm solving the constrained shortest path problem. We define an abstract, nondeterministic form of the algorithm and prove its correctness from a few simple axioms. We then define a sequence of natural refinements which can be proved to be correct and lead from the abstract algorithm to an efficient implementation due to Ulrich Lauther [Lauther 1996] and based on [Desrosiers et al. 1995]. Along the way, we also show that the abstract algorithm can be regarded as a natural extension of Moore s algorithm [Moore 1957] for solving the shortest path problem. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-003-04-0304 | |
| dc.identifier | https://lib.jucs.org/article/27350/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/7140 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 3(4): 304-319 | |
| dc.subject | abstract state machine | |
| dc.subject | software verification | |
| dc.subject | shortest path problem | |
| dc.subject | constrained shortest path problem | |
| dc.title | The Constrained Shortest Path Problem: A Case Study in Using ASMs | |
| dc.type | Research Article |