Extracting differences between regular tree grammars
Kazuma Horie, Nobutaka Suzuki · 2013
An XML document is usually stored with its schema so that the structural consistency of the document is ensured. In general, schemas are continuously updated according to changes in real world. Thus, we have to precisely know how a schema is updated to keep the validity of the XML documents. In order to know how a schema is updated, we need to extract the difference between "old" and "new" schemas. However, schemas are recently becoming larger and more complex, thus it becomes more difficult to know how a schema is updated. In this paper, we consider the problem of extracting the difference between regular tree grammars, a popular formal model of XML schema languages. We first show that the problem is NP-hard. Then we give a sufficient condition under which the problem can be solved efficiently, and present a polynomial-time algorithm for solving the problem under the sufficient condition. Finally, we show some experimental results.