一阶逻辑公式相对真度的计算形式

对二值谓词逻辑中一阶公式关于有限解释的相对真度定义进行了简化,给出其计算形式。指出一阶非闭逻辑公式的相对真度只与其中自由出现的变元有关,而非只与其中的自由变元有关;证明可以增加公式中出现的变元个数,而不会改变公式的相对真度,从而可以依据相对真度的计算形式横向研究公式间的相对真度问题。     

Satisfiability problems for propositional calculi

For each fixed set of Boolean connectives, how hard is it to determine satisfiability for formulas with only those connectives? We show that a condition sufficient for NP-completeness is that the functionx Λ ~ y be representable, and that any set of connectives not capable of representing this function has a polynomial-time satisfiability problem.     

可满足实例的归结复杂度

GRB模型是一种随机约束满足问题模型,此模型具有精确的可满足相变现象。针对实验中出现的GRB模型在相变区域产生的可满足实例都是难解的现象,利用子句宽度和归结复杂度的关系证明了GRB模型在相变点附近产生的可满足实例对于树型归结证明具有指数下界。因此从理论上证明了在相变区域产生的可满足实例对基于归结的算法是难解的。     

An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs

This paper is concerned with the application of semidefinite programming to the satisfiability problem, and in particular with using semidefinite liftings to efficiently obtain proofs of unsatisfiability. We focus on the Tseitin satisfiability instances which are known to be hard for many proof systems. For Tseitin instances based on toroidal grid graphs, we present an explicit semidefinite programming problem with dimension linear in the size of the Tseitin instance, and prove that it characterizes the satisfiability of these instances, thus providing an explicit certificate of satisfiability or unsatisfiability. Research partially supported by the Natural Sciences and Engineering Research Council of Canada.     

Automatic decidability and combinability

Verification problems can often be encoded as first-order validity or satisfiability problems. The availability of efficient automated theorem provers is a crucial pre-requisite for automating various verification tasks as well as their cooperation with specialized decision procedures for selected theories, such as Presburger Arithmetic. In this paper, we investigate how automated provers based on a form of equational reasoning, called paramodulation, can be used in verification tools. More precisely, given a theory T axiomatizing some data structure, we devise a procedure to answer the following questions. Is the satisfiability problem of T decidable by paramodulation? Can a procedure based on paramodulation for T be efficiently combined with other specialized procedures by using the Nelson-Oppen schema? Finally, if paramodulation decides the satisfiability problem of two theories, does it decide satisfiability in their union?The procedure capable of answering all questions above is based on Schematic Saturation; an inference system capable of over-approximating the inferences of paramodulation when solving satisfiability problems in a given theory T. Clause schemas derived by Schematic Saturation describe all clauses derived by paramodulation so that the answers to the questions above are obtained by checking that only finitely many different clause schemas are derived or that certain clause schemas are not derived.     

TSAT++: an Open Platform for Satisfiability Modulo Theories

This paper describes TSAT++, an open platform which realizes the lazy SAT-based approach to Satisfiability Modulo Theories (SMT). SMT is the problem of determining satisfiability of a propositional combination of T-literals, where T is a first-order theory for which a satisfiability procedure for a set of ground atoms is known. TSAT++ enjoys a modular design in which an enumerator and a theory-specific satisfiability checker cooperate in order to solve SMT. Modularity allows both different enumerators, and satisfiability checkers for different theories (or combinations of theories), to be plugged in, as far as they comply to a simple and well-defined interface. A number of optimization techniques are also implemented in TSAT++, which are independent of the modules used (and of the corresponding theory). Some experimental results are presented, showing that TSAT++, instantiated for Separation Logic, is competitive with, or faster than, state-of-the-art solvers for that very logic.     

Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances

An enhanced concept of sub-optimal reverse Horn fraction of a CNF-formula was introduced in [18]. It was shown that this fraction is very useful in effectively (almost) separating 3-colorable random graphs with fixed node-edge density from the non-3-colorable ones. A correlation between this enhanced sub-optimal reverse Horn fraction and satisfiability of random 3-SAT instances with a fixed density was observed. In this paper, we present experimental evidence that this correlation scales to larger-sized instances and that it extends to solver performances as well, both of complete and incomplete solvers. Furthermore, we give a motivation for various phases in the algorithm aHS, establishing the enhanced sub-optimal reverse Horn fraction, and we present clear evidence for the fact that the observed correlations are stronger than correlations between satisfiability and sub-optimal MAXSAT-fractions established similarly to the enhanced sub-optimal reverse Horn fraction. The latter observation is noteworthy because the correlation between satisfiability and the optimal MAXSAT-fraction is obviously 100%. AMS subject classification 90C05, 03B99, 68Q01, 68W01     

Branching-Time Logics Repeatedly Referring to States

While classical temporal logics lose track of a state as soon as a temporal operator is applied, several branching-time logics able to repeatedly refer to a state have been introduced in the literature. We study such logics by introducing a new formalism, hybrid branching-time logics, subsuming the other approaches and making the ability to refer to a state more explicit by assigning a name to it. We analyze the expressive power of hybrid branching-time logics and the complexity of their satisfiability problem. As main result, the satisfiability problem for the hybrid versions of several branching-time logics is proved to be 2EXPTIME-complete. To prove the upper bound, the automata-theoretic approach to branching-time logics is extended to hybrid logics. As a result of independent interest, the nonemptiness problem for alternating one-pebble Büchi tree automata is shown to be 2EXPTIME-complete. A common property of the logics studied is that they refer to only one state. This restriction is crucial: The ability to refer to more than one state causes a nonelementary blow-up in complexity. In particular, we prove that satisfiability for NCTL* has nonelementary complexity.     

Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic

There has been a great deal of work on characterizing the complexityof the satisfiability and validity problem for modal logics.In particular, Ladner showed that the satisfiability problemfor all logics between K and S4 is PSPACE-hard, while for S5it is NP-complete. We show that it is negative introspection,the axiom ¬K_p K¬K_p, that causes the gap: if we addthis axiom to any modal logic between K and S4, then the satisfiabilityproblem becomes NP-complete. Indeed, the satisfiability problemis NP-complete for any modal logic that includes the negativeintrospection axiom.     

半扩展规则下分解的定理证明方法

基于扩展规则的定理证明方法在一定意义上是与归结原理对偶的方法,通过子句集能否推导出所有极大项来判定可满足性.IER(improved extension rule)算法是不完备的算法,在判定子句集子空间不可满足时,并不能判定子句集的满足性,算法还需重新调用ER(extension rule)算法,降低了算法的求解效率.通过对子句集的极大项空间的研究,给出了子句集的极大项空间分解后子空间的求解方法.通过对扩展规则的研究,给出了极大项部分空间可满足性判定方法PSER(partial semi-extension rule).在IER算法判定子空间不可满足时,可以调用PSER算法判定子空间对应的补空间的可满足性,从而得到子句集的可满足性,避免了不能判定极大项子空间可满足性时需重新调用ER算法的缺点,使得IER算法更完备.在此基础上,还提出DPSER(degree partial semi-extension rule)定理证明方法.实验结果表明:所提出的DPSER和IPSER的执行效率较基于归结的有向归结算法DR、IER及NER算法有明显的提高.     

Exact satisfiability,a natural extension of set partition,and its average case behavior

The problem of determining whether a Boolean formula in conjunctive normal form is satisfiable in such a way that in each clause exactly one literal is set true, and all the other literals are set false is called the exact satisfiability problem. The exact satisfiability problem is well known to be NP-complete [5] and it contains the well known set partitioning problem as a special case. We study here the average time complexity of a simple backtracking strategy for solving the exact satisfiability problem under two probability models, the constant density model and the constant degree model. For both models we present results sharply separating classes of instances solvable in low degree polynomial time in the average from classes for which superpolynomial or exponential time is needed in the average.     

Deciding Regular Grammar Logics with Converse Through First-Order Logic

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF², which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. The translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. It is practically relevant because it makes it possible to use a decision procedure for the guarded fragment in order to decide regular grammar logics with converse. The class of regular grammar logics includes numerous logics from various application domains. A consequence of the translation is that the general satisfiability problem for every regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Other logics that can be translated into GF² include nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF² without extra machinery such as fixed-point operators.     

An artificial neural network satisfiability tester

An artificial neural network tester for the satisfiability problem of propositional calculus is presented. Satisfiability is treated as a constraint satisfaction optimization problem and, contrary to most of the existing satisfiability testers, the expressions are converted into disjunctive normal form before testing. The artificial neural network is based on the principles of harmony theory. Its basic characteristics are the simulated annealing procedure and the harmony function; the latter constitutes a measure of the satisfiability of the expression under the current truth assignment to its variables. The tester is such that: (a) the satisfiability of any expression is determined; (b) a truth assignment to the variables of the expression is output which renders true the greatest possible number of clauses; (c) all the truth assignments which render true the maximum number of clauses can be produced. © 2001 John Wiley & Sons, Inc.     

Decidable metric logics

The common metric temporal logic for continuous time were shown to be insufficient, when it was proved that they cannot express a modality suggested by Pnueli. Moreover no finite temporal logic can express all the natural generalizations of this modality. It followed that if we look for an optimal decidable metric logic we must accept infinitely many modalities, or adopt a different formalism.Here we identify a fragment of the second order monadic logic of order with the “+1” function, that expresses all the Pnueli modalities and much more. Its main advantage over the temporal logics is that it enables us to say not just that within prescribed time there is a point where some punctual event will occur, but also that within prescribed time some process that starts now (or that started before, or that will start soon) will terminate. We prove that this logic is decidable with respect to satisfiability and validity, over continuous time. The proof depends heavily on the theory of compositionality. In particular every temporal logic that has truth tables in this logic is automatically decidable. We extend this result by proving that any temporal logic, that has all its modalities defined by means more general than truth tables, in a logic stronger than the one just described, has a decidable satisfiability problem. We suggest that this monadic logic can be the framework in which temporal logics can be safely defined, with the guarantee that their satisfiability problem is decidable.     

Propositional semantics for disjunctive logic programs

In this paper we study the properties of the class of head-cycle-free extended disjunctive logic programs (HEDLPs), which includes, as a special case, all nondisjunctive extended logic programs. We show that any propositional HEDLP can be mapped in polynomial time into a propositional theory such that each model of the latter corresponds to an answer set, as defined by stable model semantics, of the former. Using this mapping, we show that many queries over HEDLPs can be determined by solving propositional satisfiability problems. Our mapping has several important implications: It establishes the NP-completeness of this class of disjunctive logic programs; it allows existing algorithms and tractable subsets for the satisfiability problem to be used in logic programming; it facilitates evaluation of the expressive power of disjunctive logic programs; and it leads to the discovery of useful similarities between stable model semantics and Clark's predicate completion.     

随机正则(k,r)-SAT问题的可满足临界

研究k-SAT问题实例中每个变元恰好出现r=2s次,且每个变元对应的正、负文字都出现s次的严格随机正则（k,r）-SAT问题.通过构造一个特殊的独立随机实验,结合一阶矩方法,给出了严格随机正则（k,r）-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等,因此得到了随机正则（k,r）-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则（k,r）-SAT问题的可满足临界值上界,而且还小于一般的随机k-SAT问题的可满足临界值.因此,这也从理论上解释了在相变点处的随机正则（k,r）-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后,数值分析结果验证了所给上界的正确性.     

Complexity of Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints Between Regular Open Terms

In this paper we study the satisfiability problem for language equations and constraints between regular open terms. We prove that: the constraint problem is PSPACE-complete, the regular language matching problem is EXPSPACE-complete even if we ask about satisfiability by regular languages, satisfiability of word-like language equations is in PSPACE, the finite solution problem is EXPSPACE-complete.     

模糊描述逻辑FALNUI的tableaux推理

分析了模糊描述逻辑FALNUI与模糊ER模型的关系,即模糊ER模型可以转化为FALNUI的知识库,并且模糊ER模型的可满足性、冗余性和包含关系等推理问题可以转化为FALNUI的包含推理问题,但FALNUI缺乏相应的推理算法.提出了一种基于描述逻辑tableaux的FALNUI的可满足性推理算法,证明了该推理算法的正确性,以及提出了FALNUI的Tbox扩展和去除方法,证明了FALNUI的包含推理问题可以转化为可满足性推理问题,并给出了FALNUI的包含推理算法.FALNUI的tableaux推理算法为模糊ER模型的可满足性、冗余性和包含关系等自动推理的实现提供了理论基础.     

Testing satisfiability of CNF formulas by computing a stable set of points

We show that a conjunctive normal form (CNF) formula F is unsatisfiable if and only if there is a set of points of the Boolean space that is stable with respect to F. So testing the satisfiability of a CNF formula reduces to looking for a stable set of points (SSP). We give some properties of SSPs and describe a simple algorithm for constructing an SSP for a CNF formula. Building an SSP can be viewed as a natural way of search space traversal. This naturalness of search space examination allows one to make use of the regularity of CNF formulas to be checked for satisfiability. We illustrate this point by showing that if a CNF F formula is symmetric with respect to a group of permutations, it is very easy to make use of this symmetry when constructing an SSP. As an example, we show that the unsatisfiability of pigeon-hole CNF formulas can be proven by examining only a set of points whose size is quadratic in the number of holes. Finally, we introduce the notion of an SSP with excluded directions and sketch a procedure of satisfiability testing based on the construction of such SSPs.     

Finding a Given Number of Solutions to a System of Fuzzy Constraints<Superscript>*</Superscript>

A minimax modification of a fuzzy constraint satisfaction problem is considered, where constraints determine not whether a given solution is feasible but the numerical value of satisfiability. The algorithm is proposed that finds a given number of solutions with the highest value of satisfiability in polynomial time for a subclass of problems with constraints invariant to some majority operator. It is important that knowing the operator itself is not required. Moreover, it is not necessary to guarantee its existence. For any system of fuzzy constraints, the algorithm either finds a given number of best solutions or declines the problem. The latter is only possible when no such operator exists.