Tree Pattern Rewriting SystemsReportar como inadecuado

Tree Pattern Rewriting Systems - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique 3 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications

Abstract : Classical verification often uses abstraction when dealing with data. On the other hand, dynamic XML-based applications have become pervasive, for instance with the ever growing importance of web services. We define here Tree Pattern Rewriting Systems TPRS as an abstract model of dynamic XML-based documents. TPRS systems generate infinite transition systems, where states are unranked and unordered trees hence possibly modeling XML documents. The guarded transition rules are described by means of tree patterns. Our main result is that given a TPRS system T, R, a tree pattern P and some integer k such that any reachable document from T has depth at most k, it is decidable albeit of non elementary complexity whether some tree satisfying P is reachable from T.

Autor: Blaise Genest - Anca Muscholl - Olivier Serre - Marc Zeitoun -



Documentos relacionados