checking determinism of regular expressions with counting

ISCAS OpenIR

	checking determinism of regular expressions with counting
	Chen Haiming; Lu Ping
	2012
会议名称	16th International Conference on Developments in Language Theory, DLT 2012
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
页码	332-343
会议日期	August 14, 2012 - August 17, 2012
会议地点	Taipei, Taiwan
收录类别	EI
ISSN	0302-9743
ISBN	9783642316524
部门归属	(1) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing 100190 China
摘要	We give characterizations of strong determinism for regular expressions with counting, based on which we present an O(\|ΣE∥E\|) time algorithm to check whether an expression E with counting is strongly deterministic where ΣE is the set of distinct symbols in E. It improves the previous upper bound of O(\|E\|³) time on the same decision problems for both standard regular expressions and regular expressions with counting. As a natural result of our work we derive a characterization of weak determinism for regular expressions with counting, which leads to a new O(\|ΣE∥E\|) time algorithm for deciding weak determinism of regular expressions with counting. © 2012 Springer-Verlag.; We give characterizations of strong determinism for regular expressions with counting, based on which we present an O(\|ΣE∥E\|) time algorithm to check whether an expression E with counting is strongly deterministic where ΣE is the set of distinct symbols in E. It improves the previous upper bound of O(\|E\|³) time on the same decision problems for both standard regular expressions and regular expressions with counting. As a natural result of our work we derive a characterization of weak determinism for regular expressions with counting, which leads to a new O(\|ΣE∥E\|) time algorithm for deciding weak determinism of regular expressions with counting. © 2012 Springer-Verlag.
关键词	Algorithms
主办者	National Taiwan University; National Science Council; Ministry of Education; Academia Sinica; European Association for Theoretical Computer Science
语种	英语
WOS记录号	WOS:000353352800014
引用统计	被引频次：12[WOS] [WOS记录] [WOS相关记录]
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15779
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Chen Haiming,Lu Ping. checking determinism of regular expressions with counting[C],2012:332-343.