Abstract
It was shown that real-world XML documents often contain errors that make their processing complicated or impossible. Having a potentially invalid XML document, our goal is to find its structural corrections with respect to a provided schema represented in DTD or XSD languages.
In this paper we propose several improvements of algorithms we introduced earlier, extend our model to support the full expressive power of regular tree grammars and we still guarantee that all the minimal corrections are found regardless the extent of document invalidity. According to experiments, our new correction algorithm outperforms the existing ones by more than two times, achieves near linear execution times in practice and works successfully on documents of sizes up to two orders of magnitude higher than those assumed so far.