Representations of Reversible Automata and State Graphs of Vector Addition Systems
Résumé
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.