SHUFFLE ON TRAJECTORIES - SYNTACTIC CONSTRAINTS

We introduce and investigate new methods to define parallel compositio n of words and languages as well as of omega-words and omega-languages . The operation of parallel composition leads to new shuffle-like oper ations defined by syntactic constraints on the usual shuffle operation . The approach is applicable to concurrency, providing a method to def ine parallel composition of processes. It is also applicable to parall el computation. The operations are introduced using a uniform method b ased on the notion of trajectory. As a consequence, we obtain a very i ntuitive geometrical interpretation of the parallel composition operat ion. These operations lead in a natural way to a large class of semiri ngs. The approach is amazingly flexible, diverse concepts from the the ory of concurrency can be introduced and studied in this framework. Fo r instance, we provide examples of applications to fairness property a nd to parallelization of non-context-free languages in terms of contex t-free and even regular languages. This paper concentrates on syntacti c constraints. Semantic constraints will be dealt with in a forthcomin g contribution. (C) 1998 - Elsevier Science B.V. All rights reserved.