On the Contribution of Backward Jumps to Instruction Sequence Expressiveness

摘要

We investigate the expressiveness of backward jumps in a frame work of formalized sequential programming called program algebra and characterize established non-uniform complexity classes in terms of instruction sequences, backward jumps and auxiliary registers.