Integer compositions and syntactic trees of repeat-until programs

In this work we study some properties of integer compositions in connection with the recognition of rational trace languages. In particular, we introduce some operations defined on integer compositions and present procedures for their computation that work in linear or in quadratic time. These procedures turn out to be useful in the analysis of syntactic trees of certain regular expressions, called repeat-until expressions, which intuitively represent programs of instructions nested in repeat-until loops. Our main aim is to show how, in some cases, such an analysis allows us to design algorithms for the recognition of (rational) trace languages defined by repeat-until expressions, which work in quadratic time independently of the concurrency relation.