一类受限正则表达式的推断算法

CORC > 软件研究所 > 软件所图书馆 > 期刊论文

	一类受限正则表达式的推断算法
	冯晓强 ; 郑黎晓 ; 陈海明
刊名	计算机科学
	2014
卷号	41 期号:4 页码:178-183
关键词	XML模式模式推断正则表达式自动机算法 XML schema Schema inference Regular expression Automata Algorithm
ISSN号	1002-137X
其他题名	Inferring Algorithm for a Subclass of Restricted Regular Expressions
中文摘要	XML模式推断问题的主要任务可以归约为从一个句子集合中推断出对应的确定型正则表达式.提出了一类在XML模式中大量出现的受限正则表达式,给出了该类正则表达式的推断算法.该算法首先根据给定的句子集合构造自动机,然后根据自动机和句子集合推断出对应的正则表达式.该算法的时间复杂度为max(O(\|V\| +\|E\|),C(L)),其中V和E分别表示自动机的节点集合和边集合,L表示句子集合中所有句子的长度之和.对算法的终止性和正确性进行了证明.
英文摘要	The problem of inferring XML schemas reduces to inferring deterministic regular expressions from a set of sentences. A subclass of restricted regular expressions which commonly occur in practical XML schemas was proposed. An algorithm for inferring this kind of regular expressions was described. The algorithm first constructs the corresponding automata according to the sentence set, then infers the regular expression from the automata and the sentence set. The complexity of the algorithm is max(O(\|V\|+\|E\|), O(L))where V and Eare the set of states and the set of edges of the constructed automata respectively, and Lis the total length of sentences. The termination and correctness of the algorithm were proved.
收录类别	CSCD
语种	中文
CSCD记录号	CSCD:5113114
公开日期	2014-12-16
内容类型	期刊论文
源URL	[http://ir.iscas.ac.cn/handle/311060/16752]
专题	软件研究所_软件所图书馆_期刊论文
推荐引用方式 GB/T 7714	冯晓强,郑黎晓,陈海明. 一类受限正则表达式的推断算法[J]. 计算机科学,2014,41(4):178-183.
APA	冯晓强,郑黎晓,&陈海明.(2014).一类受限正则表达式的推断算法.计算机科学,41(4),178-183.
MLA	冯晓强,et al."一类受限正则表达式的推断算法".计算机科学 41.4(2014):178-183.