holographic reduction: a domain changed application and its partial converse theorems

ISCAS OpenIR > 2010软件所会议论文

	holographic reduction: a domain changed application and its partial converse theorems
	Xia Mingji
	2010
Conference Name	37th International Colloquium on Automata, Languages and Programming, ICALP 2010
Source	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	666-677
Conference Date	44018
Conference Place	Bordeaux, France
Indexed Type	ei
Publish Place	Germany
ISSN	3029743
ISBN	3642141641
Department	(1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing 100190, China
English Abstract	Holographic reductions between some Holant problems and some #CSP(H d ) problems are built, where H d is some complex value binary function. By the complexity of these Holant problems, for each integer d≥2, #CSP(H d ) is in P when each variables appears at most d times, while it is #P-hard when each variables appears at most d+1 times. #CSP(H d ) counts weighted summation of graph homomorphisms from input graph G to graph H d , and the maximum occurrence of variables is the maximum degree of G. We conjecture the converse of holographic reduction holds for most of #Bi-restriction Constraint Satisfaction Problems, which can be regarded as a generalization of a known result about counting graph homomorphisms. It is proved that the converse of holographic reduction holds for some classes of problems. © 2010 Springer-Verlag Berlin Heidelberg.
Keyword	Linguistics
Sponsorship	CEA; Communaute Urbaine de Bordeaux; Conseil Regional dAquitaine; GDR Informatique Mathmatique (CNRS); INRIA; Total
Language	英语
Content Type	会议论文
URI	http://ir.iscas.ac.cn/handle/311060/8790
Collection	2010软件所会议论文
Recommended Citation GB/T 7714	Xia Mingji. holographic reduction: a domain changed application and its partial converse theorems[C]. Germany,2010:666-677.

Files in This Item:
File Name/Size	DocType	Version	Access	License
holographic reductio（199KB）			限制开放	--	Application Full Text

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

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