确定型语言的相关研究综述

作者：陈海明; 陆平

来源：集成技术, 2013, (06): 65-70.

• 正则表达式
• 确定型语言
• 算法
• 复杂度 regular expression
• deterministic language
• algorithm
• complexity

随着互联网应用的不断普及,XML(可扩展标记语言)在数据库、数据传输等方面的作用也越来越大。一般而言,XML文档的结构都是由XML模式语言来定义,比如DTD和XML Schema。文章主要对DTD和XML Schema的内容模式约束,即确定型正则表达式进行研究,分别详细介绍确定型表达式、确定型语言、及相关问题的研究现状。文章首先给出确定型表达式的定义及相关概念。接着,介绍几种确定型表达式的判定算法。然后,分析确定型语言的判定、对应确定型表达式的生成、及近似确定型表达式的生成等问题。文章最后还列举一些其他相关问题的研究。

• 单位
  计算机科学国家重点实验室; 中国科学院软件研究所