An Instruction Sequence Semigroup With Involutive Anti-Automorphisms

Download Now Date Added: Nov 2009
Format: PDF

The authors introduce algebra of instruction sequences by presenting a semigroup C in which programs can be represented without directional bias: In terms of the next instruction to be executed, C has both forward and backward instructions and a C-expression can be interpreted starting from any instruction. They provide equations for thread extraction, i.e., C's program semantics. Then they consider thread extraction compatible (anti-)homomorphisms and (anti-)automorphisms. Finally they discuss some expressiveness results.