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 |
|
| 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
(Final published version)
|
| Permalink to this page | |
