@inproceedings{eb53a2a9eda2428f89220445bd77c9a7,
title = "Tree pattern rewriting systems",
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). Their guarded transition rules are described by means of tree patterns. Our main result is that given a TPRS system , 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 matching P is reachable from T.",
author = "Blaise Genest and Anca Muscholl and Olivier Serre and Marc Zeitoun",
year = "2008",
month = jan,
day = "1",
doi = "10.1007/978-3-540-88387-6\_29",
language = "English",
isbn = "354088386X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "332--346",
booktitle = "Automated Technology for Verification and Analysis - 6th International Symposium, ATVA 2008, Proceedings",
note = "6th International Symposium on Automated Technology for Verification and Analysis, ATVA 2008 ; Conference date: 20-10-2008 Through 23-10-2008",
}