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.

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2012-05, Vol.50 (4), p.706-720
Main Authors: Bergstra, Jan A., Bethke, Inge
Format: Article
Language:English
Subjects:
Algebra
Boolean
Complexity
Computation
Computer programming
Computer Science
Frames
Mathematical analysis
Programming
Registers
Science
Semantics
Studies
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-011-9376-x