Institutional Repository
| cfi construction and balanced graphs | |
| Zhou Xiang | |
| 2009 | |
| Conference Name | 3rd International Workshop on Frontiers in Algorithmics |
| Source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Pages | 97-107 |
| Conference Date | JUN 20-23, |
| Conference Place | Hefei, PEOPLES R CHINA |
| Indexed Type | istp,ei,acm |
| Publish Place | HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY |
| Publisher | FRONTIERS IN ALGORITHMICS, PROCEEDINGS |
| ISSN | 0302-9743 |
| ISBN | 978-3-642-02269-2 |
| Department | Zhou, Xiang Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100864, Peoples R China. |
| English Abstract | 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. |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8338 |
| Collection | 2009年期刊/会议论文 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment