Quantitative Expressiveness of Instruction Sequence Classes for Computation on Single Bit Registers
arXiv:1904.08722
Abstract
The number of instructions of an instruction sequence is taken for its logical SLOC, and is abbreviated with LLOC. A notion of quantitative expressiveness is based on LLOC and in the special case of operation over a family of single bit registers a collection of elementary properties are established. A dedicated notion of interface is developed and is used for stating relevant properties of classes of instruction sequences
References in corpus (7)
- Instruction sequences with indirect jumps
- From Philosophy to Program Size
- Instruction sequence based non-uniform complexity classes
- On the expressiveness of single-pass instruction sequences
- On instruction sets for Boolean registers in program algebra
- A short introduction to program algebra with instructions for Boolean registers
- Instruction sequences expressing multiplication algorithms