A general framework for computing maximal contractions  

作　　者：Jie LUO 

机构地区：[1]State Key Laboratory of Software Development Environment,School of Computer Science and Engineering, Beihang University, Beijing 100191, China

出　　处：《Frontiers of Computer Science》2013年第1期83-94,共12页中国计算机科学前沿（英文版）

摘　　要：This paper investigates the problem of computing all maximal contractions of a given formula set F with re- spect to a consistent set A of atomic formulas and negations of atomic formulas. We first give a constructive definition of minimal inconsistent subsets and propose an algorithmic framework for computing all minimal inconsistent subsets of any given formula set. Then we present an algorithm to com- pute all maximal contractions from minimal inconsistent sub- sets. Based on the algorithmic framework and the algorithm, we propose a general framework for computing all maximal contractions. The computability of the minimal inconsistent subset and maximal contraction problems are discussed. Fi- nally, we demonstrate the ability of this framework by apply- ing it to the first-order language without variables and design an algorithm for the computation of all maximal contractions.This paper investigates the problem of computing all maximal contractions of a given formula set F with re- spect to a consistent set A of atomic formulas and negations of atomic formulas. We first give a constructive definition of minimal inconsistent subsets and propose an algorithmic framework for computing all minimal inconsistent subsets of any given formula set. Then we present an algorithm to com- pute all maximal contractions from minimal inconsistent sub- sets. Based on the algorithmic framework and the algorithm, we propose a general framework for computing all maximal contractions. The computability of the minimal inconsistent subset and maximal contraction problems are discussed. Fi- nally, we demonstrate the ability of this framework by apply- ing it to the first-order language without variables and design an algorithm for the computation of all maximal contractions.

关 键 词：maximal contraction minimal inconsistent sub- set COMPUTABILITY algorithms 

分 类 号：TP311.51[自动化与计算机技术—计算机软件与理论] TU528.01[自动化与计算机技术—计算机科学与技术]