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

arima:1479 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, December 13, 2016, Volume 25 - 2016 - Special issue CNRIA 2015 - https://doi.org/10.46298/arima.1479
Complexity of Opacity algorithm in data-centric workflow systemArticle

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

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.


Volume: Volume 25 - 2016 - Special issue CNRIA 2015
Published on: December 13, 2016
Accepted on: December 7, 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]

Consultation statistics

This page has been seen 461 times.
This article's PDF has been downloaded 507 times.