A Domain for Concurrent Termination : A Generalization of Mazurkiewicz traces

V. Diekert, P. Gastin

IBP-Litp 1995/15: Rapport de Recherche Litp / Litp research reports
 pages - Mars/March 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: A Domain for Concurrent Termination : A Generalization of Mazurkiewicz traces

Résumé : Ce papier généralise le concept de trace introduit par Mazurkiewicz à une description floue d'un comportement distribué, où une première composante donne un préfixe connu et une deuxième composante fournit une information alphabétique partielle sur les futures actions. On définit ainsi un bon domaine sémantique dans lequel la concaténation est continue par rapport aux topologies de Scott et de Lawson. A cette fin, on définit les notions de alpha-trace et de delta-trace. On établit plusieurs résultats mathématiques qui légitiment notre approche. Cette théorie est une stricte généralisation de la théorie des mots finis et infinis (avec terminaison explicite) et de la théorie des traces finies et infinies (réelles et complexes). On utilise la théorie des traces, la théorie des domaines et la topologie.

Abstract : This paper generalizes the concept of Mazurkiewicz traces to a fuzzy description of a concurrent process, where a known prefix is given in a first component and a second alphabetic component yields necessary information about future actions. This allows to define a good semantic domain where the concatenation is continuous with respect to the Scott- and to the Lawson topology. For this, we define the notion of alpha-trace and of delta-trace. We show various mathematical results proving thereby the soundness of our approach. Our theory is a proper generalization of the theory of finite and infinite words (with explicit termination) and of the theory of finite and infinite (real and complex) traces. We make use of trace theory, domain theory, and topology.

Publications internes Litp 1995 / Litp research reports 1995