ISCAS OpenIR
一类受限正则表达式的推断算法
其他题名Inferring Algorithm for a Subclass of Restricted Regular Expressions
冯晓强; 郑黎晓; 陈海明
2014
发表期刊计算机科学
ISSN1002-137X
卷号41期号:4页码:178-183
摘要XML模式推断问题的主要任务可以归约为从一个句子集合中推断出对应的确定型正则表达式.提出了一类在XML模式中大量出现的受限正则表达式,给出了该类正则表达式的推断算法.该算法首先根据给定的句子集合构造自动机,然后根据自动机和句子集合推断出对应的正则表达式.该算法的时间复杂度为max(O(|V| +|E|),C(L)),其中V和E分别表示自动机的节点集合和边集合,L表示句子集合中所有句子的长度之和.对算法的终止性和正确性进行了证明.
收录类别CSCD
其他摘要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.
关键词Xml模式 模式推断 正则表达式 自动机 算法 Xml Schema Schema Inference Regular Expression Automata Algorithm
部门归属中国科学院软件研究所计算机科学国家重点实验室 北京100190;中国科学院大学 北京100049 华侨大学计算机科学与技术学院 厦门361021 中国科学院软件研究所计算机科学国家重点实验室 北京100190
语种中文
CSCD记录号CSCD:5113114
内容类型期刊论文
URI标识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.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[冯晓强]的文章
[郑黎晓]的文章
[陈海明]的文章
百度学术
百度学术中相似的文章
[冯晓强]的文章
[郑黎晓]的文章
[陈海明]的文章
必应学术
必应学术中相似的文章
[冯晓强]的文章
[郑黎晓]的文章
[陈海明]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。