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.     

Point algebras for temporal reasoning: Algorithms and complexity

We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.     

Automata theory based on quantum logic: some characterizations

Automata theory based on quantum logic (abbr. l-valued automata theory) may be viewed as a logical approach of quantum computation. In this paper, we characterize some fundamental properties of l-valued automata theory, and discover that some properties of the truth-value lattices of the underlying logic are equivalent to certain properties of automata. More specifically (i) the transition relations of l-valued automata are extended to describe the transitions enabled by strings of input symbols, and particularly, these extensions depend on the distributivity of the truth-value lattices (Proposition 3.1); (ii) some properties of the l-valued successor and source operators and l-valued subautomata are demonstrated to be equivalent to a property of the truth-value lattices which is exactly equivalent to the distributive law (Proposition 4.3 and Corollary 4.4). This is a new characterization of Boolean algebras in the framework of l-valued automata theory; (iii) we verify that the intersection of two l-valued subautomata is still an l-valued subautomaton if and only if the multiplication (&) is distributive over the union in the truth-value lattices (Proposition 4.5), which is strictly weaker than the usual distributivity; (iv) we show that some topological characterizations in terms of the l-valued successor and source operators also rely on the distributivity of truth-value lattices (Theorem 5.6). Finally, we address some related topics for further study.     

A Decision Procedure for a Sublanguage of Set Theory Involving Monotone, Additive, and Multiplicative Functions

MLSS is a decidable sublanguage of set theory involving the predicates membership, set equality, set inclusion, and the operators union, intersection, set difference, and singleton.In this paper we extend MLSS with constructs for expressing monotonicity, additivity, and multiplicativity properties of set-to-set functions. We prove that the resulting language is decidable by reducing the problem of determining the satisfiability of its sentences to the problem of determining the satisfiability of sentences of MLSS.     

Indecomposability of free algebras in some subvarieties of residuated lattices and their bounded subreducts

In this paper, we show that free algebras in the variety of residuated lattices and some of its subvarieties are directly indecomposable and show, as a consequence, the direct indecomposability of free algebras for some classes of their bounded implicative subreducts.     

The complexity of the satisfiability problem for Krom formulas

We study the computational complexity of the satisfiability problem for Krom (CNF-2) formulas. Upper and lower bounds are obtained for several decidable classes of formulas determined by quantifier prefix and degree of predicate letters. For example, we show that determining satisfiability of Krom formulas with quantifier prefix of the form ……… is complete for deterministic exponential time, but that if the number of universal quantifiers is bounded then polynomial time suffices.     

L-fuzzy congruence classes in universal algebras

In this paper, we study fuzzy congruence relations and their classes; so-called fuzzy congruence classes in universal algebras whose truth values are in a complete lattice satisfying the infinite meet distributive law. Fuzzy congruence relations generated by a fuzzy relation are fully characterized in different ways. The main result in this paper is that, we give several Mal'cev-type characterizations for a fuzzy subset of an algebra $A$ in a given variety to be a class of some fuzzy congruence on $A$. Some equivalent conditions are also given for a variety of algebras to possess fuzzy congruence classes which are also fuzzy subuniverses. Special fuzzy congruence classes called fuzzy congruence kernels are characterized in a more general context in universal algebras.     

Classes of examples of pseudo-MV algebras, pseudo-BL algebras and divisible bounded non-commutative residuated lattices

We illustrate by classes of examples the close connections existing between pseudo-MV algebras, on the one hand, and pseudo-BL algebras and divisible bounded non-commutative residuated lattices, on the other hand. We use equivalent definitions of these algebras, as particular cases of pseudo-BCK algebras. We analyse the strongness, the pseudo-involutive center and the filters for each example.     

On the isomorphism problem of concept algebras

Weakly dicomplemented lattices are bounded lattices equipped with two unary operations to encode a negation on concepts. They have been introduced to capture the equational theory of concept algebras (Wille 2000; Kwuida 2004). They generalize Boolean algebras. Concept algebras are concept lattices, thus complete lattices, with a weak negation and a weak opposition. A special case of the representation problem for weakly dicomplemented lattices, posed in Kwuida (2004), is whether complete weakly dicomplemented lattices are isomorphic to concept algebras. In this contribution we give a negative answer to this question (Theorem 4). We also provide a new proof of a well known result due to M.H. Stone (Trans Am Math Soc 40:37–111, 1936), saying that each Boolean algebra is a field of sets (Corollary 4). Before these, we prove that the boundedness condition on the initial definition of weakly dicomplemented lattices (Definition 1) is superfluous (Theorem 1, see also Kwuida (2009)).     

Distributive mereotopology: extended distributive contact lattices

The notion of contact algebra is one of the main tools in the region based theory of space. It is an extension of Boolean algebra with an additional relation C called contact. The elements of the Boolean algebra are considered as formal representations of spatial regions as analogues of physical bodies and Boolean operations are considered as operations for constructing new regions from given ones and also to define some mereological relations between regions as part-of, overlap and underlap. The contact relation is one of the basic mereotopological relations between regions expressing some topological nature. It is used also to define some other important mereotopological relations like non-tangential inclusion, dual contact, external contact and others. Most of these definitions are given by means of the operation of Boolean complementation. There are, however, some problems related to the motivation of the operation of Boolean complementation. In order to avoid these problems we propose a generalization of the notion of contact algebra by dropping the operation of complement and replacing the Boolean part of the definition by that of a distributive lattice. First steps in this direction were made in (Düntsch et al. Lect. Notes Comput. Sci. 4136, 135–147, 2006, Düntsch et al. J. Log. Algebraic Program. 76, 18–34, 2008) presenting the notion of distributive contact lattice based on the contact relation as the only mereotopological relation. In this paper we consider as non-definable primitives the relations of contact, nontangential inclusion and dual contact, extending considerably the language of distributive contact lattices. Part I of the paper is devoted to a suitable axiomatization of the new language called extended distributive contact lattice (EDC-lattice) by means of universal first-order axioms true in all contact algebras. EDC-lattices may be considered also as an algebraic tool for a certain subarea of mereotopology, called in this paper distributive mereotopology. The main result of Part I of the paper is a representation theorem, stating that each EDC-lattice can be isomorphically embedded into a contact algebra, showing in this way that the presented axiomatization preserves the meaning of mereotopological relations without considering Boolean complementation. Part II of the paper is devoted to topological representation theory of EDC-lattices, transferring into the distributive case important results from the topological representation theory of contact algebras. It is shown that under minor additional assumptions on distributive lattices as extensionality of the definable relations of overlap or underlap one can preserve the good topological interpretations of regions as regular closed or regular open sets in topological space.     

Some Techniques for Proving Termination of the Hyperresolution Calculus

We define a semantic criterion ensuring termination of the hyperresolution calculus, which allows us to prove the decidability of certain classes of clause sets. We also define an algorithm for deciding – in polynomial time – whether a given clause set satisfies the proposed criterion. Comparisons with existing works on hyperresolution-based decision procedures are provided, showing evidence of the interest of our approach.     

Decision procedures for extensions of the theory of arrays

The theory of arrays, introduced by McCarthy in his seminal paper “Towards a mathematical science of computation,” is central to Computer Science. Unfortunately, the theory alone is not sufficient for many important verification applications such as program analysis. Motivated by this observation, we study extensions of the theory of arrays whose satisfiability problem (i.e., checking the satisfiability of conjunctions of ground literals) is decidable. In particular, we consider extensions where the indexes of arrays have the algebraic structure of Presburger arithmetic and the theory of arrays is augmented with axioms characterizing additional symbols such as dimension, sortedness, or the domain of definition of arrays. We provide methods for integrating available decision procedures for the theory of arrays and Presburger arithmetic with automatic instantiation strategies which allow us to reduce the satisfiability problem for the extension of the theory of arrays to that of the theories decided by the available procedures. Our approach aims to re-use as much as possible existing techniques so as to ease the implementation of the proposed methods. To this end, we show how to use model-theoretic, rewriting-based theorem proving (i.e., superposition), and techniques developed in the Satisfiability Modulo Theories communities to implement the decision procedures for the various extensions.      

Symbolic protocol analysis in the union of disjoint intruder theories: Combining decision procedures

Most of the decision procedures for symbolic analysis of protocols are limited to a fixed set of algebraic operators associated with a fixed intruder theory. Examples of such sets of operators comprise XOR, multiplication, abstract encryption/decryption. In this report we give an algorithm for combining decision procedures for arbitrary intruder theories with disjoint sets of operators, provided that solvability of ordered intruder constraints, a slight generalization of intruder constraints, can be decided in each theory. This is the case for most of the intruder theories for which a decision procedure has been given. In particular our result allows us to decide trace-based security properties of protocols that employ any combination of the above mentioned operators with a bounded number of sessions.     

Ideals and congruences of basic algebras

MV-algebras as well as orthomodular lattices can be seen as a particular case of so-called “basic algebras” which are an alter ego of bounded lattices whose sections are equipped with fixed antitone involutions. The class of basic algebras is an ideal variety. In the paper, we give an internal characterization of congruence kernels (ideals) and find a finite basis of ideal terms, with focus on monotone and effect basic algebras. We also axiomatize basic algebras that are subdirect products of linearly ordered ones.     

Bounded Model Checking of CTL^*

Bounded Model Checking has been recently introduced as an efficient verification method for reactive systems. This technique reduces model checking of linear temporal logic to propositional satisfiability. In this paper we first present how quantified Boolean decision procedures can replace BDDs. We introduce a bounded model checking procedure for temporal logic CTL＊ which reduces model checking to the satisfiability of quantified Boolean formulas. Our new technique avoids the space blow up of BDDs, and extends the concept of bounded model checking.     

Out of order quantifier elimination for Standard Quantified Linear Programs

In this paper, we present an out of order quantifier elimination algorithm for a class of Quantified Linear Programs (QLPs) called Standard Quantified Linear Programs (SQLPs). QLPs in general and SQLPs in particular are extremely useful constraint logic programming structures that find wide applicability in the modeling of real-time schedulability specifications; see Subramani [Subramani, K., 2005a. A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. The Computer Journal 48 (3), 259–272]. Consequently any algorithmic advance in their solution has a strong practical impact. Prior to this work, the only known approaches to the solution of QLPs involved sequential variable elimination; see Subramani [Subramani, K., 2003b. An analysis of quantified linear programs. In: Calude, C.S. et al. (Eds.), Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science. DMTCS. In: Lecture Notes in Computer Science, vol. 2731. Springer-Verlag, pp. 265–277]. In the sequential approach, the innermost quantified variable is eliminated first, followed by the variable which then becomes the innermost quantified variable and so on, until we are left with a single variable from which the satisfiability of the original formula is easily deduced. This approach is applicable in both discrete and continuous domains; however, it is to be noted that the logic demanding the sequential approach requires that the variables are discrete-valued. To the best of our knowledge, the necessity for sequential elimination over continuous-valued variables has not been investigated in the literature. The techniques used in the development of our elimination algorithm may find applications in domains such as classical logic and finite model theory. The final aspect of our research concerns the structure-preserving nature of the algorithm that we introduce here; in general, it is not known whether discrete domains admit such elimination procedures.     

Lattices of processes in graphs and congruences on ideals in distributive lattices

We consider the class of lattices of processes in graphs and its relationship to the class of all distributive lattices.Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 162–165, January–February, 1992.     

一阶子句搜索方法

子句集的可满足性判定是自动证明领域的热点之一.提出了子句搜索方法判定命题子句集Φ的可满足性,该方法查找Φ中子句的一个公共不可扩展子句C,当且仅当找到C时Φ可满足,此时C中各文字的补构成一个模型.结合部分实例化方法将子句搜索方法提升至一阶.一阶子句搜索方法可以判定子句集的M可满足性,具备终止性、正确性和完备性,是一种判定子句集可满足性的有效方法.     

Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators

The class of unquantified formulae of set theory involving Boolean operators, the powerset and singleton operators, and the equality and membership predicates is shown to have a solvable satisfiability problem.It is shown that whenever a formula in the above class is satisfiable there exists a hereditarily finite model of , whose rank is bounded by a doubly exponential expression in the number of variables occurring in .This paper was written while the author was a Visiting Professor at Courant Institute of Mathematical Sciences, New York University, U.S.A.