On algorithmic equivalence of instruction sequences for computing bit string functions
| Authors |
|
| Publication date |
2015
|
| Journal |
Fundamenta Informaticae
|
| Volume | Issue number |
138 | 4
|
| Pages (from-to) |
411-434
|
| Organisations |
-
Faculty of Science (FNWI) - Informatics Institute (IVI)
|
| Abstract |
Every partial function from bit strings of a given length to bit strings of a possibly different given length can be computed by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We look for an equivalence relation on instruction sequences of this kind that captures to a reasonable degree the intuitive notion that two instruction sequences express the same algorithm.
|
| Document type |
Article
|
| Language |
English
|
| Published at |
https://doi.org/10.3233/FI-2015-1219
|
|
Permalink to this page
|
Back
