论文部分内容阅读
XML模式推断问题的主要任务可以归约为从一个句子集合中推断出对应的确定型正则表达式.提出了一类在XML模式中大量出现的受限正则表达式,给出了该类正则表达式的推断算法.该算法首先根据给定的句子集合构造自动机,然后根据自动机和句子集合推断出对应的正则表达式.该算法的时间复杂度为max（O（｜V｜ ＋｜E｜）,C（L））,其中V和E分别表示自动机的节点集合和边集合,L表示句子集合中所有句子的长度之和.对算法的终止性和正确性进行了证明.