论文部分内容阅读
在语义Web的基础研究中，以XML为代表的半结构化数据模型是一个重要的研究方向．通常的方法是将其视为树的数据结构，与定义在树上的语言联系起来，并利用相关工具对它进行研究．这样的工具主要有两个类别：一是利用树的语法，即一个产生式系统研究树上的语言；二是从自动机的角度出发，利用树语言的验证器进行研究．本质上这两种方式是等价的，即，树的语法产生的语言类就是自动机所能接受的语言类．然而，作为产生式系统，树的语法不能对树的语言进行验证；而树的自动机虽然可以用于验证，但其非确定性使得它的计算并不容易实现．可见，就应用而言，树的语法和自动机各自受到了一些限制．为了消除这些限制，本文提出了一类与上述两种工具等价的计算模型，即递归树自动机，对此模型的计算能力进行了分析和证明，得到了它的一些性质，并介绍了该模型的一些可能的应用．文章首先从模型的应用背景，即语义网络，XML和XML Schema出发，简介了以往的一些类似的模型的情况．随后对XML Schema，的各个元素作了形式化，并在此基础上给出了递归树自动机以及它的计算的定义．接下来对模型的计算能力作了分析，证明了它与正则树语法的等价性．然后从递归树自动机的角度对正则树语言的封闭性进行了证明，并对此模型的部分判定问题的复杂度作了估计．同时，文章还介绍了将XML Schema转换为递归树自动机的算法，并利用它给XML Schema添加语义将其转换为OWL，以及将对应的XMI文档转换为RDF．最后对未来进一步的工作作了简要的讨论．