Context-Free Event Domains are recognizable

Eric Badouel 1 Philippe Darondeau 1 Jean-Claude Raoult 1
1 MICAS - Modèles et implémentation des calculs syntaxiques
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires
Abstract : The possibly non distributive event domains which arise from Winskel's event structures with binary conflict are known to coincide with the domains of configurations of Stark's trace automata. We prove that whenever the transitive reduction of the order on finite elements in an event domain is a context-free graph in the sense of Müller and Schupp, that event domain may also be generated from a finite trace automaton, where both the set of states and the concurrent alphabet are finite. We show that the set of graph grammars which generate event domains is a recursive set. We obtain altogether an effective procedure which decides from an unlabelled graph grammar whether it generates an event domain and which constructs in that case a finite trace automaton recognizing that event domain. The advantage of trace automata over unlabelled graph grammars is to provide for a more concrete and therefore more tractable representation of event domains, well suited to an automated verification of their properties.
Type de document :
Rapport
[Research Report] RR-2588, INRIA. 1995
Liste complète des métadonnées

https://hal.inria.fr/inria-00074095
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:30:36
Dernière modification le : jeudi 11 janvier 2018 - 06:21:19
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:05:02

Fichiers

Identifiants

  • HAL Id : inria-00074095, version 1

Collections

Citation

Eric Badouel, Philippe Darondeau, Jean-Claude Raoult. Context-Free Event Domains are recognizable. [Research Report] RR-2588, INRIA. 1995. 〈inria-00074095〉

Partager

Métriques

Consultations de la notice

219

Téléchargements de fichiers

248