On instruction sets for Boolean registers in program algebra
| Authors | |
|---|---|
| Publication date | 01-02-2015 |
| Number of pages | 18 |
| Publisher | Ithaca, NY: ArXiv |
| Organisations |
|
| Abstract | In program algebra, different instruction sets for Boolean registers are conceivable. In previous work on instruction sequence size complexity, we chose instruction sets for Boolean registers that contain only a few of the possible instructions. In the current paper, we study instruction sequence size bounded functional completeness of instruction sets for Boolean registers. This work is among other things a requisite for making progress with proving lower bounds of non-asymptotic instruction sequence size complexity in cases where auxiliary Boolean registers may be used. |
| Document type | Working paper |
| Note | Version 1 |
| Language | English |
| Published at | https://arxiv.org/abs/1502.00238v1 |
| Downloads |
1502.00238v1
(Submitted manuscript)
|
| Permalink to this page | |
