An Instruction Sequence Semigroup with Involutive Anti-Automorphisms

We introduce an algebra of instruction sequences by presenting asemigroup C in which programs can be represented without directionalbias: in terms of the next instruction to be executed, C has both forwardand backward instructions and a C-expression can be interpretedstarting from any instruction. We provide equations for thread extraction,i.e., C’s program semantics. Then we consider thread extractioncompatible (anti-)homomorphisms and (anti-)automorphisms. Finallywe discuss some expressiveness results.