Regularity Results for FIFO Channels

In this paper, we show that piecewiseness is central to the understanding of FIFO channel systems. Our contribution is to study the effect of iterating sets of operations, while extending and unifying previous work on both lossy and perfect FIFO systems. In particular, we show that well-quasi-orderings are important to Σ2, not only to the lossy systems of Π1. Moreover, we show that Σ2 also describes limits in a class of FIFO systems that include iterations of arbitrary sets of simultaneous read and write operations.