Approximating Traces

V. Diekert, P. Gastin

IBP-Litp 1996/26: Rapport de Recherche Litp / Litp research reports
28 pages - Juillet/July 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Approximating Traces

Résumé : Résumé : Un modèle doit avoir de nombreuses propriétés mathématiques importantes afin d'être utilisable en sémantique des systèmes concurrents. Dans ce papier, on généralise les traces (infinies) de Mazurkiewicz en ajoutant une informatisation sur les extensions possibles d'un processus. Ceci permet de définir un ordre d'approximation et une composition ayant de bonnes interactions. On obtient un domaine cohéremment complet et premier algébrique dans lequel les éléments compacts sont exactement les approximations finies des processus réels. La composition est monotone et continue par rapport à l'ordre d'approximation. On définit une distance ultramétrique naturelle qui engendre la topologie de Lawson. On obtient donc un espace métrique complet et compact dans lequel l'ensemble des approximations finies des processus est dense. De plus la composition des processus est en fait uniformément continue.

Abstract : Abstract : In order to give a semantics to concurrent processes, one needs a powerful model which enjoys many important mathematical properties. We general Mazurkiewicz (infinite) traces by adding an information concerning the possible continuations of a process. This allows to define an approximation order and a composition. We obtain a prime algebraic cohenrently complete domain where the compacts are exactly the finite approximations of actual processes. The composition is shown to be monotone and U-continuous. We define a suitable metric which induces the Lawson topology and yields a complete and compact metric space. The finite approximations of processes form a dense subset and the composition is uniformly continuous.

Publications internes Litp 1996 / Litp research reports 1996