cfi construction and balanced graphs

ISCAS OpenIR > 2009年期刊/会议论文

	cfi construction and balanced graphs
	Zhou Xiang
	2009
会议名称	3rd International Workshop on Frontiers in Algorithmics
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
页码	97-107
会议日期	JUN 20-23,
会议地点	Hefei, PEOPLES R CHINA
收录类别	istp,ei,acm
出版地	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
出版者	FRONTIERS IN ALGORITHMICS, PROCEEDINGS
ISSN	0302-9743
ISBN	978-3-642-02269-2
部门归属	Zhou, Xiang Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100864, Peoples R China.
摘要	In this article, we define a new variant of Cai-Furer-Immerman construction. With this construction and some conditions of Dawar and Richerby, we are able to show that inflationary fixed point logic with counting (IFP+C) does not capture PTIME on the class of balanced graphs.
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/8338
专题	2009年期刊/会议论文
推荐引用方式 GB/T 7714	Zhou Xiang. cfi construction and balanced graphs[C]. HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY:FRONTIERS IN ALGORITHMICS, PROCEEDINGS,2009:97-107.