Representations of Reversible Automata and State Graphs of Vector Addition Systems

Eric Badouel 1
1 PARAGRAPHE - Parallelism and Graphs
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : Using the interpretation of a place of a vector addition system as a synchronic constraint we derive a characterization of the state graphs of vector addition systems as the maximal quotients of polyhedral automata. We give a classification of the representations of reversible automata (automata in which events are local bijections on states) as full subgraphs of Schreier graphs. We describe the computation of the canonical representation of a commutative automaton (automaton that fully embedds in the Cayley graph of an abelian group). We suggest on that basis an algorithm to decide whether a finite automaton is isomorphic to the state graph of a vector addition system. The correction of this algorithm however relies on the conjecture that the state graphs of vector addition systems are torsion-free.
Type de document :
Rapport
[Research Report] RR-3490, INRIA. 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00073197
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:10:30
Dernière modification le : mercredi 16 mai 2018 - 11:23:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:37:36

Fichiers

Identifiants

  • HAL Id : inria-00073197, version 1

Citation

Eric Badouel. Representations of Reversible Automata and State Graphs of Vector Addition Systems. [Research Report] RR-3490, INRIA. 1998. 〈inria-00073197〉

Partager

Métriques

Consultations de la notice

136

Téléchargements de fichiers

385