Diouf, Mohamadou Lamine and Pinchinat, Sophie - Complexity of Opacity algorithm in data-centric workflow system

arima:1479 - Revue Africaine de la Recherche en Informatique et Mathématiques Appliquées, December 13, 2016, Volume 25 - 2016 - Special issue CNRIA 2015
Complexity of Opacity algorithm in data-centric workflow system

Authors: Diouf, Mohamadou Lamine and Pinchinat, Sophie

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.


Source : oai:HAL:hal-01351970v2
Volume: Volume 25 - 2016 - Special issue CNRIA 2015
Published on: December 13, 2016
Submitted on: December 13, 2016
Keywords: Opacity,Complexity,data-centric workflow systems,Structured documents,Complexité,Opacité,système à flots de tâches,artefact,documents structurés.,[INFO] Computer Science [cs]


Share

Consultation statistics

This page has been seen 103 times.
This article's PDF has been downloaded 130 times.