The following paper has been published in Information & Computation:
Posets With Interfaces as a Model for Concurrency
Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemiański
We introduce posets with interfaces (iposets) and generalise their standard
serial composition to a new gluing composition. In the partial order
semantics of concurrency, interfaces and gluing allow modelling events that
extend in time and across components. Alternativelytaking a decompositional
view, interfaces allow cutting through events, while serial composition may
only cut through edges of a poset. We show that iposets under gluing
composition form a category, which generalises the monoid of posets under
serial composition up to isomorphism. They form a 2-category when a
subsumption order and a lax tensor in the form of a non-commutative parallel
composition are added, which generalises the interchange monoids used for
modelling series-parallel posets. We also study the gluing-parallel
hierarchy of iposets, which generalises the standard series-parallel one.
The class of gluing-parallel iposets contains that of series-parallel posets
and the class of interval orders, which are well studied in concurrency
theory, too. We also show that it is strictly contained in the class of all
iposets by identifying several forbidden substructures.
I’m pleased to announce I’ve had a paper accepted for presentation at The 34th Symposium on Implementation and Application of Functional Languages
(https://ifl22.github.io <https://ifl22.github.io/>). The paper is entitled: How to fold and color a map: Comparing Use-Cases of Tree-Fold vs Fold-Left.
You may view the article here https://drive.google.com/file/d/1-65beERt9UylSmxgsWe-gcl3Hz8JvjzC/view?usp=…
as it is not yet available on /lrde/doc, pending an IT issue.
In this article we examine some consequences of computation order of two different conceptual implementations of the fold function. We explore a set of performance- and accuracy-based experiments on two implementations of this function. In particular, we contrast the traditional fold-left implementation with another approach we refer to as tree-fold. It is often implicitly supposed that the binary operation in question has constant complexity. We explore several application areas which diverge from that assumption: rational arithmetic, floating-point arithmetic, and Binary Decisions Diagram construction. These are binary operations which degrade in performance as the fold iteration progresses. We show that these types of binary operations are good candidates for tree-fold.