Deciding determinism of unary languages

ISCAS OpenIR

	Deciding determinism of unary languages
	Lu, P; Peng, FF; Chen, HM; Zheng, LX
	2015
发表期刊	INFORMATION AND COMPUTATION
ISSN	0890-5401
卷号	245 页码:181-196
摘要	In this paper, we investigate the complexity of deciding determinism of unary languages. First, we give a method to derive a set of arithmetic progressions from a regular expression Eover a unary alphabet, and establish relations between numbers represented by these arithmetic progressions and words in L( E). Next, we define a problem relating to arithmetic progressions and investigate the complexity of this problem. Then by a reduction from this problem we show that deciding determinism of unary languages iscoNPcomplete. Finally, we extend our derivation method to expressions with counting, and prove that deciding whether an expression over a unary alphabet with counting defines a deterministic language is in Pi(p)(2). We also establish a tight upper bound for the size of the minimal DFA for expressions with counting. (C) 2015 Elsevier Inc. Allrightsreserved.; In this paper, we investigate the complexity of deciding determinism of unary languages. First, we give a method to derive a set of arithmetic progressions from a regular expression Eover a unary alphabet, and establish relations between numbers represented by these arithmetic progressions and words in L( E). Next, we define a problem relating to arithmetic progressions and investigate the complexity of this problem. Then by a reduction from this problem we show that deciding determinism of unary languages iscoNPcomplete. Finally, we extend our derivation method to expressions with counting, and prove that deciding whether an expression over a unary alphabet with counting defines a deterministic language is in Pi(p)(2). We also establish a tight upper bound for the size of the minimal DFA for expressions with counting. (C) 2015 Elsevier Inc. Allrightsreserved.
收录类别	SCI
关键词	Regular Expressions Regular Expressions With Counting Deterministic Languages Minimal Dfa Conp-complete Pi(p)(2)
部门归属	Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China. Chinese Acad Sci, Grad Univ, Beijing 100190, Peoples R China. Univ Chinese Acad Sci, Beijing, Peoples R China. Huaqiao Univ, Coll Comp Sci & Technol, Xiamen 361021, Fujian, Peoples R China.
语种	英语
WOS记录号	WOS:000368899100012
引用统计	被引频次：4[WOS] [WOS记录] [WOS相关记录]
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/17428
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Lu, P,Peng, FF,Chen, HM,et al. Deciding determinism of unary languages[J]. INFORMATION AND COMPUTATION,2015,245:181-196.
APA	Lu, P,Peng, FF,Chen, HM,&Zheng, LX.(2015).Deciding determinism of unary languages.INFORMATION AND COMPUTATION,245,181-196.
MLA	Lu, P,et al."Deciding determinism of unary languages".INFORMATION AND COMPUTATION 245(2015):181-196.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
1-s2.0-S089054011500（515KB）			开放获取	使用许可	请求全文