确定性表达式及其子类的理论问题与工具研究

Deterministic regular expressions are widely used in XML and other fields. However the related theoretical studies for this kind of expressions currently cannot meet the need of practical work. This project will study several most important problems in the theoretical studies for deterministic expressions. Presently the most difficulty in using this kind of expressions is that they do not have a syntax definition. This has become an important reason for restricting the use of deterministic expressions, and also a reason for using DTDs and XML Schemas that do not conform specifications in practice. Meanwhile, most of DTDs and XML Schemas use subclasses of deterministic expressions, such as SOREs and CHAREs. Hence the main objectives of this project are to develop syntax definitions for deterministic expressions and their subclasses, and study tools for automatically generating deterministic expressions based on these definitions. For the situation where there is not any schema for the XML files, we will study how to infer deterministic expressions or their subclasses for these files. For some important decision problems in deterministic languages, we will try to investigate theoretical properties and develop new algorithms, and hope to get some computational complexity results. For strongly deterministic regular expressions, we want to establish the relations between strongly deterministic expressions and deterministic expressions. By using these relations, we intend to design a linear time algorithm for deciding strong determinism of regular expressions, and find automata whose determinism will indicates determinism of regular expressions with counting. All these theoretical results will greatly promote the use of deterministic regular expressions in practice.

确定性表达式在XML以及其它领域有着很多应用，然而相关的理论研究目前还远不能满足实际工作的需要。本项目将对其中迫切需要解决的问题进行深入、系统的研究。目前使用确定性表达式的最主要的困难在于这类表达式没有语法定义，这已成为制约确定性表达式应用以及在实际当中使用不符合规范的DTDs和XML Schemas的重要因素。另外在实际中，还经常使用确定性表达式的一些子类。因此，本项目研究确定性表达式及其子类的语法表示问题，和基于语法的确定性表达式生成工具。对于模式缺失的情况，则需要研究确定性表达式及子类的推断问题。对于确定性语言研究中极为重要的若干判定问题，我们将进行理论与算法研究，希望得到新的复杂度结论和算法。对于强确定性表达式，则希望得到线性判定算法，并通过建立确定性与强确定性表达式之间的联系，得到带数字出现的确定性表达式的自动机刻画。这些研究结果，将对确定性表达式的更好应用产生积极而深远的影响。

确定性表达式在XML以及其它领域有着很多应用，本项目对其中迫切需要解决的问题进行深入、系统的研究，包括语法表示和推断问题、确定性语言与强确定性表达式的判定算法、和生成工具。本项目执行结果超额完成了研究计划，取得的主要进展和结果如下。.(1) 在确定性表达式的语法表示研究方面，1) 提出了标准确定性表达式的第一个文法。2) 证明标准确定性表达式所属的文法类为上下文无关文法。3) 给出了判定有效文法产生式的规则。上述工作，迈出了解决语法表示问题的重要一步。.(2) 在确定性语言的理论与判定算法研究方面，1) 标准确定性正则语言的判定。a) 证明了当字母表固定时判定一个最小确定性自动机是否刻画了一个确定性正则语言是NL（非确定对数空间）完全的。b) 证明了判定一个单字母表的标准正则表达式是否对应于一个确定性正则表达式是coNP完全的。2) 带数字出现的确定性正则语言的判定。我们通过研究单字母确定性正则语言的判定，给出这个问题的一个复杂度下界。3) 字符单次出现确定性正则表达式（SORE）所刻画语言的判定。给出了这个问题在不同条件下所对应的复杂度。4) 限界的字符单次出现确定性正则语言的判定。给出了该问题在不同条件下所对应的复杂度。.(3) 在强、弱确定性表达式判定算法研究方面，1) 提出了强确定性表达式的第一个线性判定算法。 2) 分别提出了无序正则表达式的第一个强、弱确定性判定算法。3) 分别提出了带无序与带数字出现的正则表达式的第一个强、弱确定性判定算法。.(4) 在工具研究方面，设计并实现了一组确定性表达式生成、判定与诊断工具。.(5) 在确定性表达式及子类的推断算法研究方面，1) 针对已有的XML子类研究中存在的不足，开展了网络数据的获取与实验研究，并得到了新的研究结果。2) 基于上述数据，提出了多个确定性表达式的新子类及其推断算法。.(6) 已发表和录用17篇研究论文。