Traces Infinies

P Gastin, A Petit

IBP-Litp 1994/28: Rapport de Recherche Litp / Litp research reports
94 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Traces Infinies

Résumé : Ce rapport est le contenu du Chapitre sur les traces infinies du livre Book of Traces édité par V. Diekert et G. Rozenberg à paraître chez World Scientific (Singapore).
Différentes notions de traces infinies sont introduites et étudiées : les traces réelles, les traces complexes et les traces transfinies.
On s'intéresse ensuite à la structure d'ordre partiel définie par la relation préfixe. On prouve des résultats de complétude et d'algébricité pour l'ensemble des traces réelles et l'ensemble des traces transfinies. On en déduit que l'ensemble des traces réelles est le complété au sens des ordres partiels de l'ensemble des traces finies.
Puis, on introduit une distance ultramétrique sur l'ensemble des traces complexes et on montre que cet espace topologique compact est le complété topologique, pour cette métrique, de l'ensemble des traces finies.
Finalement, une étude très complète des familles de langages rationnels et de langages reconnaissables est menée pour les traces réelles et pour les traces complexes.

Abstract : This report contains the chapter on infinite traces of the Book of Traces edited by V. Diekert and G. Rozenberg to appear in World Scientific (Singapore).
Different notions of infinite traces are introduced and studied: real traces, complex traces and transfinite traces..
Next, we focus on the partial order set structure induced by the prefix relation on real traces and on transfinite traces. We prove completeness results and algebraicity results for the poset of real traces and for the poset transfinite traces. The poset of real traces is in fact the ideal completion of the poset of finite traces.
Then, we define an ultra metric on the set of complex traces. We prove that this metric space is compact and is the metric completion of the monoid of finite traces.
Finally, we deeply investigate the properties of the rational languages and of the recognizable languages of real traces and of complex traces.

Publications internes Litp 1994 / Litp research reports 1994