中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 软件研究所
  3. 软件所图书馆
  4. 2010软件所会议论文
holographic reduction: a domain changed application and its partial converse theorems

文献类型：会议论文

作者Xia Mingji
出版日期2010
会议名称37th International Colloquium on Automata, Languages and Programming, ICALP 2010
会议日期44018
会议地点Bordeaux, France
关键词Linguistics
页码666-677
英文摘要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.
收录类别EI
会议主办者CEA; Communaute Urbaine de Bordeaux; Conseil Regional dAquitaine; GDR Informatique Mathmatique (CNRS); INRIA; Total
会议录Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
会议录出版地Germany
语种英语
ISSN号3029743
ISBN号3642141641
源URL[http://124.16.136.157/handle/311060/8790]  
专题软件研究所_软件所图书馆_2010软件所会议论文
推荐引用方式
GB/T 7714		 Xia Mingji. holographic reduction: a domain changed application and its partial converse theorems[C]. 见:37th International Colloquium on Automata, Languages and Programming, ICALP 2010. Bordeaux, France. 44018.

入库方式： OAI收割

来源：软件研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。