Regularity Results for FIFO Channels

We identify a proper subclass of regular languages, the piecewise languages, which only allow iteration of sets of letters. For example, a(b+c)* is piecewise. We show that piecewiseness plays a key role in establishing regularity results about single and multiple channel systems. These results contrast sharply with the fact that for channel systems described with regular languages these same questions are generally undecidable.