Polynomial algorithm of limited propositional deduction

	Polynomial algorithm of limited propositional deduction
	Shi, ZZ; Liao, LJ
	1999-08-01
发表期刊	SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES
ISSN	1006-9321
卷号	42 期号:4 页码:418-424
摘要	For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a backtracking search program for propositional satisfiability problems to make search efficient. The efficiency is gained in two ways: One is to use the algorithm to derive literals so as to overcome the ambiguities in search. The other is to exploit the consequence sets of unbound atoms generated during limited deduction as a heuristic measure for possible choices. The experiments have shown remarkable improvement in reducing search space.
关键词	limited propositional deduction polynomial algorithm problem of propositional satisfiability constraint satisfaction problem
收录类别	SCI
语种	英语
WOS研究方向	Engineering ; Materials Science
WOS类目	Engineering, Multidisciplinary ; Materials Science, Multidisciplinary
WOS记录号	WOS:000082228000010
出版者	SCIENCE PRESS
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/13280
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Shi, ZZ
作者单位	Chinese Acad Sci, Comp Technol Inst, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Shi, ZZ,Liao, LJ. Polynomial algorithm of limited propositional deduction[J]. SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES,1999,42(4):418-424.
APA	Shi, ZZ,&Liao, LJ.(1999).Polynomial algorithm of limited propositional deduction.SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES,42(4),418-424.
MLA	Shi, ZZ,et al."Polynomial algorithm of limited propositional deduction".SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES 42.4(1999):418-424.