| An Instruction Sequence Semigroup with Involutive Anti-Automorphisms (2009) | |||||||||
Abstract | |||||||||
| 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, and we distinguish behavioral equivalence and congruence. Then we consider thread extraction compatible (anti-)homomorphisms and (anti-)automorphisms. Finally we axiomatize structural congruence under which we can exclude chained jumps and discuss some expressiveness results.. Comment: 25 pages, 2 tables | |||||||||
Details der Publikation | |||||||||
| |||||||||