Mohamadou Lamine Diouf ; Sophie Pinchinat - Complexité de l'algorithme de l'opacité dans les systèmes Workflows centrés sur les documents

arima:1479 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, 13 décembre 2016, Volume 25 - 2016 - Numéro spécial CNRIA 2015 - https://doi.org/10.46298/arima.1479
Complexité de l'algorithme de l'opacité dans les systèmes Workflows centrés sur les documentsArticle

Auteurs : Mohamadou Lamine Diouf 1,2; Sophie Pinchinat ORCID3

[en]
A property (of an object) is opaque to an observer when he or she cannot deduce the property from its set of observations. If each observer is attached to a given set of properties (the so-called secrets), then the system is said to be opaque if each secret is opaque to the corresponding observer. We study in this paper, the complexity of opacity algorithm in data-centric workflows systems. We show that the complexity of this algorithm is EXPTIME-complete. Using the reduction problem, whe show that we can reduce the complexity of opacity problem to wellknow problem, the intersection of nonemptyness problem of Tree automata in polynomial time.

[fr]
Une propriété d'un objet est dit opaque pour un observateur si celui-ci ne peut déduire que la propriété est satisfaite sur la base de l'observation qu'il a de cet objet. Supposons qu'un certain de nombre de propriétés (appelées secrets) soient attachées à chaque intervenant d'un système, nous dirons alors que le systéme lui-même est opaque si chaque secret d'un observateur lui est opaque: il ne peut percer aucun des secrets qui lui ont été attachés. Dans ce papier, on se propose d'étudier la complexité du problème de l'opacité des artefacts d'un système à flots de tâches(système workflow). Nous présentons une formalisation optimale du prob-lème de l'opacité dans ces systèmes workflows. Nous étudions ensuite la complexité de l'algorithme de l'opacité pour ces systèmes.


Volume : Volume 25 - 2016 - Numéro spécial CNRIA 2015
Publié le : 13 décembre 2016
Accepté le : 7 décembre 2016
Soumis le : 13 décembre 2016
Mots-clés : [INFO]Computer Science [cs], [en] Opacity, Complexity, data-centric workflow systems, Structured documents; [fr] Complexité, Opacité, système à flots de tâches, artefact, documents structurés.

Statistiques de consultation

Cette page a été consultée 625 fois.
Le PDF de cet article a été téléchargé 630 fois.