An Instruction Sequence Semigroup with Involutive Anti-Automorphisms

Published in Volume XIX, 2009, pages 57-92

Authors: J.A. Bergstra and A. Ponse

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.

Full Text (PDF)

References

[1] J.W. de Bakker and J.I. Zucker. Processes and the denotational semantics of concurrency. Information and Control, 54(1-2):70-120,1982.

[2] A. Barros and T. Hou. A constructive version of AIP revisited. Technical report PRG0802, University of Amsterdam, January 2008. Available via www.science.uva.nl/research/prog/publications.html.

[3] J.A. Bergstra and I. Bethke. Polarized process algebra and program equivalence. In J.C.M. Baeten, J.K. Lenstra, J. Parrow, G.J. Woeginger, eds., Proceedings of ICALP 2003, LNCS 2719, pages 1-21, Springer-Verlag, 2003.

[4] J.A. Bergstra and I. Bethke. Polarized process algebra with reactive composition. Theoretical Computer Science, 343(3):285-304, 2005. [5] J.A. Bergstra and J.W. Klop. Process algebra for synchronous communication. Information and Control, 60(1-3):109-137, 1984.

[6] J.A. Bergstra and M.E. Loots. Program algebra for component code. Formal Aspects of Computing, 12(1):1-17, 2000.

[7] J.A. Bergstra and M.E. Loots. Program algebra for sequential code. Journal of Logic and Algebraic Programming, 51(2):125-156, 2002.

[8] J.A. Bergstra and A. Ponse. Combining programs and state machines. Journal of Logic and Algebraic Programming 51(2):175-192, 2002.

[9] J.A. Bergstra and A. Ponse. An instruction sequence semigroup with repeaters. arXiv:0810.1151v1 [cs.PL] at http://arxiv.org/, 2008.

[10] George Crabb. English Synonyms Explained, in Alphabetical Order: With Copious Illustrations and Examples Drawn from the Best Writers. Published by Baldwin, Cradock, 1818. Original from the New York Public Library, Digitized Sep 25, 2006, 904 pages.

[11] M. Hazewinkel. Encyclopaedia of Mathematics: an updated and annotated translation of the Soviet “Mathematical Encyclopaedia”. Springer-Verlag, 2002.

[12] W.D. Maurer. A theory of computer instructions. Science of Computer Programming, 60:244-273, 2006. (A shorter version of this paper was published in the Journal of the ACM, 13(2): 226-235, 1966.)

[13] W.D. Maurer. Partially defined computer instructions and guards. Science of Computer Programming, 72(3):220-239, 2008.

[14] A. Ponse and M.B. van der Zwaag. An introduction to program and thread algebra. In A. Beckmann et al. (editors), Logical Approaches to Computational Barriers: Proceedings CiE 2006, LNCS 3988, pages 445-458, Springer-Verlag, 2006.

[15] T.D. Vu. Denotational semantics for thread algebra. Journal of Logic and Algebraic Programming, 74(2):94-111, 2008.

Bibtex

@article{sacscuza:bergstra2009aisswia,
  title={An Instruction Sequence Semigroup with Involutive Anti-Automorphisms},
  author={J.A. Bergstra and A. Ponse},
  journal={Scientific Annals of Computer Science},
  volume={19},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2009},
  pages={57--92},
  publisher={``A.I. Cuza'' University Press}
}