| MAX(1)和MARG(1)中公式改名的复杂性 |
| |
| 引用本文： | 许道云,董改芳,王健.MAX(1)和MARG(1)中公式改名的复杂性[J].软件学报,2006,17(7):1517-1526. |
| |
| 作者姓名： | 许道云 董改芳 王健 |
| |
| 作者单位： | 贵州大,学计算机科学系,贵州,贵阳,550025;内蒙古农业大学,计算机与信息工程学院,内蒙古,呼和浩特,010018;软件工程国家重点实验室(武汉大学),湖北,武汉,430072 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant Nos.60463001, 10410638 (国家自然科学基金); the Special Foundation for Improving Scientific Research Condition of Guizhou Province of China (贵州省高层次人才科研条件特助经费);the Government Foundation of Gu |
| |
| 摘 要： | 改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题"对于给定的CNF公式H和F是否存在一个变元(或文字)改名ψ使得ψ(H)=F?"的计算复杂性.MAX(1)和MARG(1)是极小不可满足公式的两个子类,这两个子类中的公式可以用树表示.树同构的判定问题在线性时间内是可解的.证明了对于MAX(1)和MARG(1)中的公式,文字改名问题在线性时间内可解,变元改名问题在平方次时间内可解.
|
| 关 键 词： | 计算复杂性 改名 极小不可满足公式 |
| 收稿时间： | 2004-02-12 |
| 修稿时间： | 7/8/2005 12:00:00 AM |
Complexities of Renaming for Formulas in MAX(1) and MARG(1) |
| |
| XU Dao-Yun,DONG Gai-Fang and WANG Jian.Complexities of Renaming for Formulas in MAX(1) and MARG(1)[J].Journal of Software,2006,17(7):1517-1526. |
| |
| Authors: | XU Dao-Yun DONG Gai-Fang and WANG Jian |
| |
| Affiliation: | 1,Department of Computer Science, Guizhou University, Guiyang 550025, China;2,College of Computer and Information Engineering, Inner Mongolia Agricultural University, Huhehaote 010018, China;2,State Key Laboratory of Software Engineering (Wuhan University |
| |
| Abstract: | A renaming is a function mapping propositional variable to itself or its complement, a variable renaming is a permutation over the set of propositional variables of a formula, and a literal renaming is a combination of a renaming and a variable renaming. Renaming for CNF formulas may help to improve DPLL algorithm. This paper investigates the complexity of decision problem: for propositional CNF formulas H and F, does there exist a variable (or literal) renaming such that (H)=F? Both MAX(1) and MARG(1) are subclasses of the minimal unsatisfiable formulas, and formulas in these subclasses can be represented by trees. The decision problem of isomorphism for trees is solvable in linear time. Formulas in the MAX(1) and MARG(1), it is shown that the literal renaming problems are solvable in linear time, and the variable renaming problems are solvable in quadratic time. |
| |
| Keywords: | complexity renaming minimal unsatisfiable formula |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
