A Classification and Closure Properties of Languages for Describing Concurrent System Behaviours

Article type: Research Article

Authors: Szijártó, Miklós

Affiliations: Dept. of Numerical and Computer Math. L. Eötvös Univ. Budapest

Abstract: The correspondence between sequential program schemes and formal languages is well known (Blikle and Mazurkiewicz (1972), Engelfriet (1974)). The situation is more complicated in the case of parallel program schemes, and trace languages (Mazurkiewicz (1977)) have been introduced to describe them. We introduce the concept of the closure of a language on a so called independence relation on the alphabet of the language, and formulate several theorems about them and the trace languages. We investigate the closedness properties of Chomsky classes under closure on independence relations, and as a special case we derive a new necessary and sufficient condition for the regularity of the commutative closure of a language.

Keywords: Formal languages, independence relation, trace languages, closure of languages on an independence relation

DOI: 10.3233/FI-1981-4305

Journal: Fundamenta Informaticae, vol. 4, no. 3, pp. 531-549, 1981