25 citations · 637 across the 113 of their papers we have counts for
26 papers · 1 filter
Quantitative Expressiveness of Instruction Sequence Classes for Computation on Single Bit Registers
Jan A. Bergstra
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 t…
Program algebra for Turing-machine programs
J. A. Bergstra, C. A. Middelburg
This paper presents an algebraic theory of instruction sequences with instructions for Turing tapes as basic instructions, the behaviours produced by the instruction sequences conc…
A short introduction to program algebra with instructions for Boolean registers
J. A. Bergstra, C. A. Middelburg
A parameterized algebraic theory of instruction sequences, objects that represent the behaviours produced by instruction sequences under execution, and objects that represent the b…
Axioms for behavioural congruence of single-pass instruction sequences
J. A. Bergstra, C. A. Middelburg
In program algebra, an algebraic theory of single-pass instruction sequences, three congruences on instruction sequences are paid attention to: instruction sequence congruence, str…
On instruction sets for Boolean registers in program algebra
J. A. Bergstra, C. A. Middelburg
In previous work carried out in the setting of program algebra, including work in the area of instruction sequence size complexity, we chose instruction sets for Boolean registers…
Long multiplication by instruction sequences with backward jump instructions
J. A. Bergstra, C. A. Middelburg
For each function on bit strings, its restriction to bit strings of any given length can be computed by a finite instruction sequence that contains only instructions to set and get…
Instruction sequences expressing multiplication algorithms
J. A. Bergstra, C. A. Middelburg
For each function on bit strings, its restriction to bit strings of any given length can be computed by a finite instruction sequence that contains only instructions to set and get…
Instruction sequence expressions for the secure hash algorithm SHA-256
J. A. Bergstra, C. A. Middelburg
The secure hash function SHA-256 is a function on bit strings. This means that its restriction to the bit strings of any given length can be computed by a finite instruction sequen…
Putting Instruction Sequences into Effect
Jan A. Bergstra
An attempt is made to define the concept of execution of an instruction sequence. It is found to be a special case of directly putting into effect of an instruction sequence. Direc…
On the behaviours produced by instruction sequences under execution
J. A. Bergstra, C. A. Middelburg
We study several aspects of the behaviours produced by instruction sequences under execution in the setting of the algebraic theory of processes known as ACP. We use ACP to describ…
Steering Fragments of Instruction Sequences
Jan A. Bergstra
A steering fragment of an instruction sequence consists of a sequence of steering instructions. These are decision points involving the check of a propositional statement in sequen…
Functional units for natural numbers
J. A. Bergstra, C. A. Middelburg
Interaction with services provided by an execution environment forms part of the behaviours exhibited by instruction sequences under execution. Mechanisms related to the kind of in…
A progression ring for interfaces of instruction sequences, threads, and services
Jan A. Bergstra, Alban Ponse
We define focus-method interfaces and some connections between such interfaces and instruction sequences, giving rise to instruction sequence components. We provide a flexible and…
Indirect jumps improve instruction sequence performance
J. A. Bergstra, C. A. Middelburg
Instruction sequences with direct and indirect jump instructions are as expressive as instruction sequences with direct jump instructions only. We show that, in the case where the…
Instruction sequence notations with probabilistic instructions
J. A. Bergstra, C. A. Middelburg
This paper concerns instruction sequences that contain probabilistic instructions, i.e. instructions that are themselves probabilistic by nature. We propose several kinds of probab…
A protocol for instruction stream processing
J. A. Bergstra, C. A. Middelburg
The behaviour produced by an instruction sequence under execution is a behaviour to be controlled by some execution environment: each step performed actuates the processing of an i…
Transmission protocols for instruction streams
J. A. Bergstra, C. A. Middelburg
Threads as considered in thread algebra model behaviours to be controlled by some execution environment: upon each action performed by a thread, a reply from its execution environm…
Instruction sequences for the production of processes
J. A. Bergstra, C. A. Middelburg
Single-pass instruction sequences under execution are considered to produce behaviours to be controlled by some execution environment. Threads as considered in thread algebra model…
On the expressiveness of single-pass instruction sequences
J. A. Bergstra, C. A. Middelburg
We perceive programs as single-pass instruction sequences. A single-pass instruction sequence under execution is considered to produce a behaviour to be controlled by some executio…
Mechanistic Behavior of Single-Pass Instruction Sequences
Jan A. Bergstra, Mark B. van der Zwaag
Earlier work on program and thread algebra detailed the functional, observable behavior of programs under execution. In this article we add the modeling of unobservable, mechanisti…
Thread extraction for polyadic instruction sequences
J. A. Bergstra, C. A. Middelburg
In this paper, we study the phenomenon that instruction sequences are split into fragments which somehow produce a joint behaviour. In order to bring this phenomenon better into th…
Programming an interpreter using molecular dynamics
J. A. Bergstra, C. A. Middelburg
PGA (ProGram Algebra) is an algebra of programs which concerns programs in their simplest form: sequences of instructions. Molecular dynamics is a simple model of computation devel…
Program algebra with a jump-shift instruction
J. A. Bergstra, C. A. Middelburg
We study sequential programs that are instruction sequences with jump-shift instructions in the setting of PGA (ProGram Algebra). Jump-shift instructions preceding a jump instructi…
Instruction sequences with indirect jumps
J. A. Bergstra, C. A. Middelburg
We study sequential programs that are instruction sequences with direct and indirect jump instructions. The intuition is that indirect jump instructions are jump instructions where…