Thread Algebra

The groundwork for the work outlined on this website is an algebraic theory of single-pass instruction sequences, called program algebra, and an algebraic theory of mathematical objects that represent in a direct way the behaviours produced by instruction sequences under execution, called basic thread algebra. The development of basic thread algebra has led to a lot of other work that is at most loosely related. This work mainly concerns the development of extensions of basic thread algebra and investigations using these extensions.

The extensions concerned include extensions to deal with the interaction between programs under execution and components of their execution environment, the kinds of interleaving appropriate for non-distributed and distributed multi-threaded programs, program overlaying, and probabilistic computation. The investigations include investigations of basic ideas from the practice of micro-architectures, the merits of program parallelization for speeding up instruction processing, the role of the operating unit size in load/store instruction set architectures, and issues concerning the use of dynamic data structures in programming.

Refereed papers

J. A. Bergstra and I. Bethke (2003). 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. doi:10.1007/3-540-45061-0_1

J. A. Bergstra and I. Bethke (2005). Polarized process algebra with reactive composition. Theoretical Computer Science, 343(3):285–304. doi:10.1016/j.tcs.2005.06.014 (freely available)

J. A. Bergstra and C. A. Middelburg (2006). Thread algebra with multi-level strategies. Fundamenta Informaticae, 71(2–3):153–182. Retrievable from http://content.iospress.com/articles/fundamenta-informaticae/fi71-2-3-02 (postprint at http://staff.fnwi.uva.nl/c.a.middelburg/papers/pre-FunInf-06.pdf)

J. A. Bergstra, I. Bethke, and A. Ponse (2007a). Decision problems for pushdown threads. Acta Informatica, 44(2):75–90. doi:10.1007/s00236-007-0040-5 (freely available)

J. A. Bergstra, I. Bethke, and A. Ponse (2007b). Thread algebra and risk assessment services. In C. Dimitracopoulos, L. Newelski, and D. Normann, editors, Logic Colloquium 2005, pages 1–17. Springer-Verlag. doi:10.1017/CBO9780511546464.003

J. A. Bergstra and C. A.Middelburg (2007a). Maurer computers with single-thread control. Fundamenta Informaticae, 80(4):333–362. Retrievable from http://content.iospress.com/articles/fundamenta-informaticae/fi80-4-01 (postprint at http://staff.fnwi.uva.nl/c.a.middelburg/papers/pre-FunInf-07.pdf)

J. A. Bergstra and C. A. Middelburg (2007b). Synchronous cooperation for explicit multi-threading. Acta Informatica, 44(7–8):525–569. doi:10.1007/s00236-007-0057-9 (freely available)

J. A. Bergstra and C. A. Middelburg (2007c). Thread algebra for strategic interleaving. Formal Aspects of Computing, 19(4):445–474. doi:10.1007/s00165-007-0024-9 (freely available)

J. A. Bergstra and C. A. Middelburg (2007d). A thread algebra with multi-level strategic interleaving. Theory of Computing Systems, 41(1):3–32. doi:10.1007/s00224-006-1337-4 (freely available)

J. A. Bergstra and C. A. Middelburg (2008). Distributed strategic interleaving with load balancing. Future Generation Computer Systems, 24(6):530–548. doi:10.1016/j.future.2007.08.001 (postprint at http://staff.fnwi.uva.nl/c.a.middelburg/papers/pre-FGCS-08.pdf)

A. Ponse and M. B. van der Zwaag (2008). Risk assessment for one-counter threads. Theory of Computing Systems, 43(3–4):563–582. doi:10.1007/s00224-007-9034-5 (freely available)

J. A. Bergstra and C. A. Middelburg (2010a). Data linkage dynamics with shedding. Fundamenta Informaticae, 103(1–4):31–52. doi:10.3233/FI-2010-317 (postprint: arXiv:0806.4034v2 [cs.LO])

J. A. Bergstra and C. A. Middelburg (2010b). On the operating unit size of load/store architectures. Mathematical Structures in Computer Science, 20(3):395–417. doi:10.1017/S0960129509990314 (postprint: arXiv:0711.0838v2 [cs.AR])

J. A. Bergstra and C. A. Middelburg (2010c). A thread calculus with molecular dynamics. Information and Computation, 208(7):817–844. doi:10.1016/j.ic.2010.01.004 (freely available)

J. A. Bergstra and C. A. Middelburg (2011). Thread algebra for poly-threading. Formal Aspects of Computing, 23(4):567–538. doi:10.1007/s00165-011-0178-3 (freely available)

J. A. Bergstra and C. A. Middelburg (2013). Data linkage algebra, data linkage dynamics, and priority rewriting. Fundamenta Informaticae, 128(4):367–412. doi:10.3233/FI-2013-950 (postprint: arXiv:0804.4565v4 [cs.LO])

J. A. Bergstra and C. A. Middelburg (2015). Probabilistic thread algebra. Scientific Annals of Computer Science, 25(2):211–243. doi:10.7561/SACS.2015.2.211 (freely available)

 

Papers are ordered by year of publication. If two or more publications have the same year of publication, then they are further ordered by surnames of the authors. If two or more publications have the same year of publication and the same surnames of the authors, then they are further ordered by title of the paper.
Advertisements