Published in Volume XXI, Issue 2, 2011, pages 283-310

Authors: J.A. Bergstra, C.A. Middelburg

Abstract

In this paper, we study the phenomenon that instruction sequences are split into fragments which somehow produce a joint behaviour. In order to bring this phenomenon better into the picture, we formalize a simple mechanism by which several instruction sequence fragments can produce a joint behaviour. We also show that, even in the case of this simple mechanism, it is a non-trivial matter to explain by means of a translation into a single instruction sequence what takes place on execution of a collection of instruction sequence fragments.

Full Text (PDF)

References

[1] K. Arnold and J. Gosling. The Java Programming Language. AddisonWesley, Reading, MA, 1996.

[2] J. A. Bergstra and I. Bethke. Polarized process algebra and program equivalence. In J. C. M. Baeten, J. K. Lenstra, J. Parrow, and G. J. Woeginger, editors, Proceedings 30th ICALP, volume 2719 of Lecture Notes in Computer Science, pages 1-21. Springer-Verlag, 2003.

[3] J. A. Bergstra and I. Bethke. Predictable and reliable program code: Virtual machine based projection semantics. In J. A. Bergstra and M. Burgess, editors, Handbook of Network and Systems Administration,
pages 653-685. Elsevier, Amsterdam, 2007.

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

[5] J. A. Bergstra and C. A. Middelburg. Instruction sequences with indirect jumps. Scientific Annals of Computer Science, 17:19-46, 2007.

[6] J. A. Bergstra and C. A. Middelburg. Thread algebra for strategic interleaving. Formal Aspects of Computing, 19(4):445-474, 2007.

[7] J. A. Bergstra and C. A. Middelburg. Program algebra with a jump-shift instruction. Journal of Applied Logic, 6(4):553-563, 2008.

[8] J. A. Bergstra and C. A. Middelburg. Instruction sequences with dynamically instantiated instructions. Fundamenta Informaticae, 96(1-2):27-48, 2009.

[9] J. A. Bergstra and C. A. Middelburg. Thread algebra for poly-threading. Formal Aspects of Computing, 23(4):567-538, 2011.

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

[11] J. Bishop and N. Horspool. C# Concisely. Addison-Wesley, Reading, MA, 2004.

[12] E. Cohen. Seperation and reduction. In R. Backhouse and J. N. Oliveira, editors, MCP 2000, volume 1837 of Lecture Notes in Computer Science, pages 45-59. Springer-Verlag, 2000.

[13] D. Kozen. A completeness theorem for Kleene algebras and the algebra of regular events. Information and Computation, 110(2):366-390, 1994.

[14] A. Ponse and M. B. van der Zwaag. An introduction to program and thread algebra. In A. Beckmann et al., editors, CiE 2006, volume 3988 of Lecture Notes in Computer Science, pages 445-458. Springer-Verlag, 2006.

[15] D. Sannella and A. Tarlecki. Algebraic preliminaries. In E. Astesiano, H.-J. Kreowski, and B. Krieg-Br¨uckner, editors, Algebraic Foundations of Systems Specification, pages 13-30. Springer-Verlag, Berlin, 1999.

[16] M. Wirsing. Algebraic specification. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 675-788. Elsevier, Amsterdam, 1990.

Bibtex

@article{sacscuza:bergstra2011tefpis,
  title={Thread Extraction for Polyadic Instruction Sequences},
  author={J.A. Bergstra and C.A. Middelburg},
  journal={Scientific Annals of Computer Science},
  volume={21},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2011},
  pages={283--310},
  publisher={``A.I. Cuza'' University Press}
}