Published in Volume XIX, 2009, pages 57-92

Authors: J.A. Bergstra and A. Ponse


We introduce an 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. We provide equations for thread extraction,
i.e., C’s program semantics. Then we consider thread extraction
compatible (anti-)homomorphisms and (anti-)automorphisms. Finally
we discuss some expressiveness results.

Full Text (PDF)


  title={An Instruction Sequence Semigroup with Involutive Anti-Automorphisms},
  author={J.A. Bergstra and A. Ponse},
  journal={Scientific Annals of Computer Science},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  publisher={``A.I. Cuza'' University Press}