中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Title:
一类受限正则表达式的推断算法
Alternative Title: Inferring Algorithm for a Subclass of Restricted Regular Expressions
Author: 冯晓强 ; 郑黎晓 ; 陈海明
Keyword: XML模式 ; 模式推断 ; 正则表达式 ; 自动机 ; 算法 ; XML schema ; Schema inference ; Regular expression ; Automata ; Algorithm
Source: 计算机科学
Issued Date: 2014
Volume: 41, Issue:4, Pages:178-183
Indexed Type: CSCD
Department: 中国科学院软件研究所计算机科学国家重点实验室 北京100190;中国科学院大学 北京100049 华侨大学计算机科学与技术学院 厦门361021 中国科学院软件研究所计算机科学国家重点实验室 北京100190
Abstract: XML模式推断问题的主要任务可以归约为从一个句子集合中推断出对应的确定型正则表达式.提出了一类在XML模式中大量出现的受限正则表达式,给出了该类正则表达式的推断算法.该算法首先根据给定的句子集合构造自动机,然后根据自动机和句子集合推断出对应的正则表达式.该算法的时间复杂度为max(O(|V| +|E|),C(L)),其中V和E分别表示自动机的节点集合和边集合,L表示句子集合中所有句子的长度之和.对算法的终止性和正确性进行了证明.
English Abstract: 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.
Language: 中文
Citation statistics:
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/16752
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
冯晓强,郑黎晓,陈海明. 一类受限正则表达式的推断算法[J]. 计算机科学,2014-01-01,41(4):178-183.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[冯晓强]'s Articles
[郑黎晓]'s Articles
[陈海明]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[冯晓强]‘s Articles
[郑黎晓]‘s Articles
[陈海明]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace