checking determinism of regular expressions with counting

ISCAS OpenIR

	checking determinism of regular expressions with counting
	Chen Haiming; Lu Ping
	2012
Conference Name	16th International Conference on Developments in Language Theory, DLT 2012
Source	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	332-343
Conference Date	August 14, 2012 - August 17, 2012
Conference Place	Taipei, Taiwan
Indexed Type	EI
ISSN	0302-9743
ISBN	9783642316524
Department	(1) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing 100190 China
English Abstract	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.
Keyword	Algorithms
Sponsorship	National Taiwan University; National Science Council; Ministry of Education; Academia Sinica; European Association for Theoretical Computer Science
Language	英语
WOS ID	WOS:000353352800014
Citation statistics	Cited Times:12[WOS] [WOS Record] [Related Records in WOS]
Content Type	会议论文
URI	http://ir.iscas.ac.cn/handle/311060/15779
Collection	中国科学院软件研究所
Recommended Citation GB/T 7714	Chen Haiming,Lu Ping. checking determinism of regular expressions with counting[C],2012:332-343.

Files in This Item:
There are no files associated with this item.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Institution:
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh

中国科学院软件研究所机构知识库