Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Decidability and Complexity of Simulation Preorder for Data-Centric Web Services
verfasst von : Lakhdar Akroun, Boualem Benatallah, Lhouari Nourine, Farouk Toumani
Erschienen in: Service-Oriented Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper studies the problem of checking the simulation preorder for data-centric services. It focuses more specifically on the underlying decidability and complexity issues in the framework of the Colombo model [1]. We show that the simulation test is
exptime
-complete for Colombo services without any access to the database (noted
Colombo
DB
= ∅
) and
2exptime
-complete when only bounded databases are considered (the obtained model is noted
Colombo
bound
). This is a decidability border since we have shown in previous work that the simulation test for unbounded Colombo is undecidable. Moreover, as a side effect of this work, we establish a correspondance between
Colombo
DB
= ∅
, restricted to equality, and Guarded Variable Automata (GVA) [2]. As a consequence, we derive EXPTIME-completeness of simulation for GVA.