Institutional Repository
| reducing symmetries to generate easier sat instances | |
| Zhang Jian; Zhuo Huang | |
| 2005 | |
| Source | Electronic Notes in Theoretical Computer Science
 |
| Volume | 125Issue:3Pages:149-164 |
| English Abstract | Finding countermodels is an effective way of disproving false conjectures. In first-order predicate logic, model finding is an undecidable problem. But if a finite model exists, it can be found by exhaustive search. The finite model generation problem in the first-order logic can also be translated to the satisfiability problem in the propositional logic. But a direct translation may not be very efficient. This paper discusses how to take the symmetries into account so as to make the resulting problem easier. A static method for adding constraints is presented, which can be thought of as an approximation of the least number heuristic (LNH). Also described is a dynamic method, which asks a model searcher like SEM to generate a set of partial models, and then gives each partial model to a propositional prover. The two methods are analyzed, and compared with each other. |
| Indexed Type | ei |
| Keyword | Finite Model Searching Sat Symmetries The Least Number Heuristic |
| Department | 计算机科学国家重点实验室 |
| Language | 英语 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/3130 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | Zhang Jian,Zhuo Huang. reducing symmetries to generate easier sat instances[J]. Electronic Notes in Theoretical Computer Science,2005,125(3):149-164. |
| APA | Zhang Jian,&Zhuo Huang.(2005).reducing symmetries to generate easier sat instances.Electronic Notes in Theoretical Computer Science,125(3),149-164. |
| MLA | Zhang Jian,et al."reducing symmetries to generate easier sat instances".Electronic Notes in Theoretical Computer Science 125.3(2005):149-164. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| 200512503149.pdf（253KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment