Expressive Equivalence and Succinctness of Parametrized Automata with respect to Finite Memory Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

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

Résumé

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.
Fichier principal
Vignette du fichier
FOR-MOVES_2015_paper_1.pdf (411 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01224144 , version 1 (04-11-2015)

Identifiants

  • HAL Id : hal-01224144 , version 1

Citer

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⟩
253 Consultations
502 Téléchargements

Partager

Gmail Facebook X LinkedIn More