Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00073197
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 12:10:30 PM
Last modification on : Thursday, February 11, 2021 - 2:48:04 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:37:36 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

168

Files downloads

444