An Instruction Sequence Semigroup with Involutive Anti-Automorphisms

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. Then we consider thread extraction compatible (anti-)homomorphisms and (anti-)automorphisms. Finally we discuss some expressiveness results.

36 pages, 1 table

References in corpus (2)

• Instruction sequences and non-uniform complexity theory
• Periodic Single-Pass Instruction Sequences

Cited by in corpus (7)

• Instruction sequence based non-uniform complexity classes
• Instruction sequence expressions for the secure hash algorithm SHA-256
• Instruction sequence notations with probabilistic instructions
• Instruction sequences expressing multiplication algorithms
• Periodic Single-Pass Instruction Sequences
• Long multiplication by instruction sequences with backward jump instructions
• Expressiveness and Extensions of an Instruction Sequence Semigroup