The Petri net synthesis problem for automatic graphs

Eric Badouel 1 Philippe Darondeau 2
2 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Automatic graphs are possibly infinite graphs with a rational presentation by finite automata; they include grids as a particular case, and Sénizergues has shown in a seminal work that they are an extension of deterministic pushdown graphs. Here, we propose a procedure that decides from the automatic presentation of a graph whether it may be realized isomorphically by the reachable state graph of some finite Petri net, with transitions in bijection with labels of edges. As automatic graphs cover more concurrent systems than pushdown graphs, this procedure improves over, and indeed subsumes, the net synthesis procedure studied earlier for pushdown graphs.
Type de document :
Rapport
[Research Report] RR-4661, INRIA. 2002
Liste complète des métadonnées

https://hal.inria.fr/inria-00071924
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 19:16:47
Dernière modification le : vendredi 16 novembre 2018 - 01:23:52
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:44:48

Fichiers

Identifiants

  • HAL Id : inria-00071924, version 1

Citation

Eric Badouel, Philippe Darondeau. The Petri net synthesis problem for automatic graphs. [Research Report] RR-4661, INRIA. 2002. 〈inria-00071924〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

143