Paper Info
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 gener- ate infinite transition systems, where states are unranked and unordered trees (hence possibly modeling XML documents). Their guarded transi- tion 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 matching P is reachable from T.
Year
DOI
Venue
2008
10.1007/978-3-540-88387-6_29
Automated Technology for Verification and Analysis
Keywords
Field
DocType
dynamic xml-based document,guarded transition rule,pis reachable,thas depth,infinite transition system,tree pattern rewriting systems,reachable document,tree pattern,unordered tree,dynamic xml-based application,tprs system,web service,xml document
Integer,Discrete mathematics,Abstraction,XML,Computer science,XML validation,Decidability,Theoretical computer science,Turing machine,Rewriting,Web service
Conference
Volume
ISSN
Citations 
5311
0302-9743
11
PageRank 
References 
Authors
0.69
13
4
Name
Order
Citations
PageRank
Blaise Genest130425.09
Anca Muscholl2117974.92
olivier serre328822.02
Marc Zeitoun428824.51