Guarded Variable Automata over Infinite Alphabets - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

Guarded Variable Automata over Infinite Alphabets

Résumé

We define guarded variable automata (GVAs), a simple extension of finite automata over infinite alphabets. In this model the transitions are labelled by letters or variables ranging over an infinite alphabet and guarded by conjunction of equalities and disequalities. GVAs are well-suited for modeling component-based applications such as web services. They are closed under intersection, union, concatenation and Kleene operator, and their nonemptiness problem is PSPACE-complete. We show that the simulation preorder of GVAs is decidable. Our proof relies on the characterization of the simulation by means of games and strategies. This result can be applied to service composition synthesis.

Dates et versions

hal-00914779 , version 1 (06-12-2013)

Identifiants

Citer

Walid Belkhir, Yannick Chevalier, Michael Rusinowitch. Guarded Variable Automata over Infinite Alphabets. 2013. ⟨hal-00914779⟩
257 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More