Expressive Equivalence and Succinctness of Parametrized Automata with respect to Finite Memory Automata

Tushant Jha 1 Walid Belkhir 2, 1 Yannick Chevalier 3, * Michael Rusinowitch 1
* Auteur correspondant
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We compare parametrized automata, a class of automata recently introduced by the authors, against finite memory automata with non-deterministic assignment, an existing class of automata used to model services. We prove that both classes have the same expressive power, while parametrized automata can be exponentially succinct in some cases. We then prove that deciding simulation preorder for parametrized automata is EXPTIME-complete, extending an earlier result showing it in EXPTIME.
Type de document :
Communication dans un congrès
FOR-MOVES 2015: FORmal MOdeling and VErification of Service-based systems, Nov 2015, Goa, India
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01224144
Contributeur : Walid Belkhir <>
Soumis le : mercredi 4 novembre 2015 - 10:49:04
Dernière modification le : mercredi 12 septembre 2018 - 17:46:03
Document(s) archivé(s) le : vendredi 5 février 2016 - 10:35:57

Fichier

FOR-MOVES_2015_paper_1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01224144, version 1

Citation

Tushant Jha, Walid Belkhir, Yannick Chevalier, Michael Rusinowitch. Expressive Equivalence and Succinctness of Parametrized Automata with respect to Finite Memory Automata. FOR-MOVES 2015: FORmal MOdeling and VErification of Service-based systems, Nov 2015, Goa, India. 〈hal-01224144〉

Partager

Métriques

Consultations de la notice

522

Téléchargements de fichiers

825