Automata theory based on lattice-ordered semirings

doi:10.1007/s00500-010-0565-3

CSpace > 数学所

	Automata theory based on lattice-ordered semirings
	Lu, Xian; Shang, Yun; Lu, Ruqian
	2011-02-01
发表期刊	SOFT COMPUTING
ISSN	1432-7643
卷号	15 期号:2 页码:269-280
摘要	In this paper, definitions of K automata, K regular languages, K regular expressions and K regular grammars based on lattice-ordered semirings are given. It is shown that KNFA is equivalent to KDFA under some finite condition, the Pump Lemma holds if K is finite, and K epsilon NFA is equivalent to KNFA. Further, it is verified that the concatenation of K regular languages remains a K regular language. Similar to classical cases and automata theory based on lattice-ordered monoids, it is also found that KNFA, K regular expressions and K regular grammars are equivalent to each other when K is a complete lattice.
关键词	Lattice-ordered semirings K automata K regular languages K regular expressions K regular grammars
DOI	10.1007/s00500-010-0565-3
语种	英语
资助项目	NSFC[60496324] ; NSFC[6002530760234010] ; NSFC[60603002] ; Pre-973 Project[2001CCA03000] ; 863 High-Tech Project[2001AA113130] ; 973 Project[2001CB312004] ; CAS Brain and Mind Science Project ; China Postdoctoral Science Foundation
WOS研究方向	Computer Science
WOS类目	Computer Science, Artificial Intelligence ; Computer Science, Interdisciplinary Applications
WOS记录号	WOS:000287593200006
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/28368
专题	数学所
通讯作者	Shang, Yun
作者单位	Acad Mil Med Sci, Acad Sinica, Inst Math, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Lu, Xian,Shang, Yun,Lu, Ruqian. Automata theory based on lattice-ordered semirings[J]. SOFT COMPUTING,2011,15(2):269-280.
APA	Lu, Xian,Shang, Yun,&Lu, Ruqian.(2011).Automata theory based on lattice-ordered semirings.SOFT COMPUTING,15(2),269-280.
MLA	Lu, Xian,et al."Automata theory based on lattice-ordered semirings".SOFT COMPUTING 15.2(2011):269-280.