![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
Abstract
A regular hedge grammar is a formal method to specify XML schema. An XML document can be viewed as an ordered labeled tree. Given an XML schema, finding the sequence of changes with minimum cost is not just of theoretical interest. This problem can be modeled, as given, as an ordered labeled tree (forest) F and as a regular hedge grammar P. We consider the minimum edit distance required to transform the forest F into F′ so that F′ is exactly matched by P. By introducing a leaf forest, we design an algorithm for solving this problem in time O(F 2 P(F + log P)), where F is the size of the forest and P is the size of the grammar. To our knowledge, this is the first algorithm to transform an XML document (ordered labeled tree) to conform to the schema (tree grammar).