A Polynomial Model for Logics with a Prime Power Number of Truth Values

This paper is concerned with a polynomial model (residue class ring) for a given q-valued propositional logic (where q is a power of a prime integer). This model allows to transfer logic problems into algebraic terms, resulting in an immediate computational approach to Knowledge Based Systems based on multi-valued logics. By means of this new approach, we have extended an already existent algebraic model to logics with a prime power number of truth values, while also getting more straightforward proofs and a more direct enunciation of the central theorem of this model.     

Data structures for symbolic multi-valued model-checking

Multi-valued logics provide an interesting alternative to classical boolean logic for modeling and reasoning about systems. Such logics can be used for reasoning about partially-specified systems, effectively encode vacuity detection and query-checking problems, help in detecting inconsistencies, and many others.In our earlier work, we identified a useful family of multi-valued logics: those specified over finite distributive lattices where negation preserves involution, i.e., for every element a of the logic. Such structures are called quasi-boolean algebras, and model-checking over these not only extends the domain of applicability of automated reasoning to new problems, but can also speed up solutions to some classical verification problems.Symbolic model-checking over quasi-boolean algebras can be cast in terms of operations over multi-valued sets: sets whose membership functions are multi-valued. In this paper, we propose and empirically evaluate several choices for implementing multi-valued sets with decision diagrams. In particular, we describe two major approaches: (1) representing the multi-valued membership function canonically, using MDDs or ADDs; (2) representing multi-valued sets as a collection of classical sets, using a vector of either MBTDDs or BDDs. The naive implementation of (2) includes having a classical set for each value of the algebra. We exploit a result of lattice theory to reduce the number of such sets that need to be represented.The major contribution of this paper is the evaluation of the different implementations of multi-valued sets, done via a series of experiments and using several case studies.

A uniform framework for weighted decision diagrams and its implementation

This paper introduces a generic framework for OBDD variants with weighted edges. It covers many boolean and multi-valued OBDD-variants that have been studied in the literature and applied to the symbolic representation and manipulation of discrete functions. Our framework supports reasoning about reducedness and canonicity of new OBDD-variants and provides a platform for the implementation and comparison of OBDD-variants. Furthermore, we introduce a new multi-valued OBDD-variant, called normalized algebraic decision diagram, which supports min/max-operations and turns out to be very useful for, e.g., integer linear programming and model checking probabilistic systems. Finally, we explain the main features of an implementation of a newly developed BDD-package, called JINC, which relies on our generic notion of weighted decision diagrams, and realizes various synthesis algorithms, reordering techniques and transformation algorithms for boolean and multi-terminal OBDDs, with or without edge-attributes, and their zero-suppressed variants.     

Semiring induced valuation algebras: Exact and approximate local computation algorithms

Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra. There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.     

Probabilistic Logic over Paths

We introduce a probabilistic modal logic PPL extending the work of [Ronald Fagin, Joseph Y. Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Information and Computation, 87(1,2):78–128, 1990; Ronald Fagin and Joseph Y. Halpern. Reasoning about knowledge and probability. Journal of the ACM, 41(2):340–367, 1994] by allowing arbitrary nesting of a path probabilistic operator and we prove its completeness. We prove that our logic is strictly more expressive than other logics such as the logics cited above. By considering a probabilistic extension of CTL we show that this additional expressive power is really needed in some applications.     

Replaceability and computational equivalence for monotone boolean functions

Summary Replacement rules have played an important role in the study of monotone boolean function complexity. In this paper, notions of replaceability and computational equivalence are formulated in an abstract algebraic setting, and examined in detail for finite distributive lattices — the appropriate algebraic context for monotone boolean functions. It is shown that when computing an element f of a finite distributive lattice D, the elements of D partition into classes of computationally equivalent elements, and define a quotient of D in which all intervals of the form [t f, t f] are boolean. This quotient is an abstract simplicial complex with respect to ordering by replaceability. Other results include generalisations and extensions of known theorems concerning replacement rules for monotone boolean networks. Possible applications of computational equivalence in developing upper and lower bounds on monotone boolean function complexity are indicated, and new directions of research both abstract mathematical and computational, are suggested.     

A new modal logic for reasoning about space: spatial propositional neighborhood logic

It is widely accepted that spatial reasoning plays a central role in artificial intelligence, for it has a wide variety of potential applications, e.g., in robotics, geographical information systems, and medical analysis and diagnosis. While spatial reasoning has been extensively studied at the algebraic level, modal logics for spatial reasoning have received less attention in the literature. In this paper we propose a new modal logic, called spatial propositional neighborhood logic (SpPNL for short) for spatial reasoning through directional relations. We study the expressive power of SpPNL, we show that it is able to express meaningful spatial statements, we prove a representation theorem for abstract spatial frames, and we devise a (non-terminating) sound and complete tableaux-based deduction system for it. Finally, we compare SpPNL with the well-known algebraic spatial reasoning system called rectangle algebra.      

A spatial equational logic for the applied π-calculus

Spatial logics have been proposed to reason locally and modularly on algebraic models of distributed systems. In this paper we define the spatial equational logic A π L whose models are processes of the applied π-calculus. This extension of the π-calculus allows term manipulation and records communications as aliases in a frame, thus augmenting the predefined underlying equational theory. Our logic allows one to reason locally either on frames or on processes, thanks to static and dynamic spatial operators. We study the logical equivalences induced by various relevant fragments of A π L, and show in particular that the whole logic induces a coarser equivalence than structural congruence. We give characteristic formulae for some of these equivalences and for static equivalence. Going further into the exploration of A π L’s expressivity, we also show that it can eliminate standard term quantification.     

A Language for Verification and Manipulation of Web Documents: (Extended Abstract)

In this paper we develop the language theory underpinning the logical framework PLF. This language features lambda abstraction with patterns and application via pattern-matching. Reductions are allowed in patterns. The framework is particularly suited as a metalanguage for encoding rewriting logics and logical systems where proof terms have a special syntactic constraints, as in term rewriting systems, and rule-based languages. PLF is a conservative extension of the well-known Edinburgh Logical Framework LF. Because of sophisticated pattern matching facilities PLF is suitable for verification and manipulation of HXML documents.     

Generating Model Checkers from Algebraic Specifications

There is a great deal of research aimed toward the development of temporal logics and model checking algorithms which can be used to verify properties of systems. In this paper, we present a methodology and supporting tools which allow researchers and practitioners to automatically generate model checking algorithms for temporal logics from algebraic specifications. These tools are extensions of algebraic compiler generation tools and are used to specify model checkers as mappings of the form , where L _s is a temporal logic source language and L _t is a target language representing sets of states of a model M, such that . The algebraic specifications for a model checker define the logic source language, the target language representing sets of states in a model, and the embedding of the source language into the target language. Since users can modify and extend existing specifications or write original specifications, new model checking algorithms for new temporal logics can be easily and quickly developed; this allows the user more time to experiment with the logic and its model checking algorithm instead of developing its implementation. Here we show how this algebraic framework can be used to specify model checking algorithms for CTL, a real-time CTL, CTL*, and a custom extension called CTL ^e that makes use of propositions labeling the edges as well as the nodes of a model. We also show how the target language can be changed to a language of binary decision diagrams to generate symbolic model checkers from algebraic specifications.     

基于双格的多值模型的精化关系与对称化简

多值模型是传统布尔模型的扩展。与布尔模型相比,多值模型更适合对包含不确定和不一致信息的软件系统进行建模。为了解决模型检测时的状态爆炸问题,研究了对基于双格的多值模型的对称化简方法。提出了一种新的多值模型的精化关系,证明其保持对[μ]演算公式的模型检测结果的正确性。定义多值模型的对称化简商结构,证明商结构与原模型之间存在互为精化的关系,因此对[μ]演算公式的模型检测在二者上可以得到相同的结果。     

Knowledge Representation

Abstract

In this semi-expository note, we first recall that every boolean function f of n variables is determined uniquely by a certain subset S of the nodes of the hypercube Q". We then propose the subgraph of Q_n induced by S as a realization of f, and call it the graph of a boolean function. We observe that boolean functions of the same type always have the same graph, but the converse does not hold. We conclude with the open question which suggests itself from a confrontation of the disjunctive and conjunctive normal forms of a boolean function.     

Symbolic Reasoning with Weighted and Normalized Decision Diagrams

Several variants of Bryant's ordered binary decision diagrams have been suggested in the literature to reason about discrete functions. In this paper, we introduce a generic notion of weighted decision diagrams that captures many of them and present criteria for canonicity. As a special instance of such weighted diagrams, we introduce a new BDD-variant for real-valued functions, called normalized algebraic decision diagrams. Regarding the number of nodes and arithmetic operations like addition and multiplication, these normalized diagrams are as efficient as factored edge-valued binary decision diagrams, while several other operators, like the calculation of extrema, minimum or maximum of two functions or the switch from real-valued functions to boolean functions through a given threshold, are more efficient for normalized diagrams than for their factored counterpart.     

Local multi-valued logics in modular expert systems

Abstract

Abstract. In this paper we describe an approach to the problem of dealing with uncertainty by means of finite multi-valued logics in modular expert systems, and the results obtained. The modularity of the systems allows us to address two main characteristics of human problem-solving: the adaptation of general knowledge to particular problems and the dependency of the management of uncertainty on the different subtasks being implemented in the modules of the system, i.e. different modules can have different local multiple-valued logics as part of their local deductive mechanisms. Although the results obtained are general, we use, throughout the paper, examples of a medical expert system that has been designed using a modular language called MILORD-II, that implements them showing the practical interest of the theoretical concepts involved.     

A New Algebraic Tool for Automatic Theorem Provers

The concepts of implicates and implicants are widely used in several fields of Automated Reasoning. Particularly, our research group has developed several techniques that allow us to reduce efficiently the size of the input, and therefore the complexity of the problem. These techniques are based on obtaining and using implicit information that is collected in terms of unitary implicates and implicants. Thus, we require efficient algorithms to calculate them. In classical propositional logic it is easy to obtain efficient algorithms to calculate the set of unitary implicants and implicates of a formula. In temporal logics, contrary to what we see in classical propositional logic, these sets may contain infinitely many members. Thus, in order to calculate them in an efficient way, we have to base the calculation on the theoretical study of how these sets behave. Such a study reveals the need to make a generalization of Lattice Theory, which is very important in Computational Algebra. In this paper we introduce the multisemilattice structure as a generalization of the semilattice structure. Such a structure is proposed as a particular type of poset. Subsequently, we offer an equivalent algebraic characterization based on non-deterministic operators and with a weakly associative property. We also show that from the structure of multisemilattice we can obtain an algebraic characterization of the multilattice structure. This paper concludes by showing the relevance of the multisemilattice structure in the design of algorithms aimed at calculating unitary implicates and implicants in temporal logics. Concretely, we show that it is possible to design efficient algorithms to calculate the unitary implicants/implicates only if the unitary formulae set has the multisemilattice structure.     

Polynomial closure and unambiguous product

This article is a contribution to the algebraic theory of automata, but it also contains an application to Büchi’s sequential calculus. The polynomial closure of a class of languagesC is the set of languages that are finite unions of languages of the formL ₀ a ₁ L ₁ ···a _nL_n, where thea _i’s are letters and theL _i’s are elements ofC. Our main result is an algebraic characterization, via the syntactic monoid, of the polynomial closure of a variety of languages. We show that the algebraic operation corresponding to the polynomial closure is a certain Mal’cev product of varieties. This result has several consequences. We first study the concatenation hierarchies similar to the dot-depth hierarchy, obtained by counting the number of alternations between boolean operations and concatenation. For instance, we show that level 3/2 of the Straubing hierarchy is decidable and we give a simplified proof of the partial result of Cowan on level 2. We propose a general conjecture for these hierarchies. We also show that if a language and its complement are in the polynomial closure of a variety of languages, then this language can be written as a disjoint union of marked unambiguous products of languages of the variety. This allows us to extend the results of Thomas on quantifier hierarchies of first-order logic.     

Boolean dominated MV-algebras

In this paper we study an obvious generalization of the hyperarchimedean MV-algebras: boolean dominated MV-algebras. Particularly we point out the wide difference between the class of the hyperarchimedean MV-algebras and the class of the boolean dominated MV-algebras.     

Modalities in linear logic weaker than the exponential “of course”: Algebraic and relational semantics

We present a semantic study of a family of modal intuitionistic linear systems, providing various logics with both an algebraic semantics and a relational semantics, to obtain completeness results. We call modality a unary operator on formulas which satisfies only one rale (regularity), and we consider any subsetW of a list of axioms which defines the exponential of course of linear logic. We define an algebraic semantics by interpreting the modality as a unary operation on an IL-algebra. Then we introduce a relational semantics based on pretopologies with an additional binary relationr between information states. The interpretation of is defined in a suitable way, which differs from the traditional one in classical modal logic. We prove that such models provide a complete semantics for our minimal modal system, as well as, by requiring the suitable conditions onr (in the spirit of correspondence theory), for any of its extensions axiomatized by any subsetW as above. We also prove an embedding theorem for modal IL-algebras into complete ones and, after introducing the notion of general frame, we apply it to obtain a duality between general frames and modal IL-algebras.     

A Constructive Object Oriented Modeling Language for Information Systems

One of the central aspects in an Information System is the meaning of data in the external world and the information carried by them. We propose a Constructive Object Oriented Modeling Language (COOML) for information systems, based on a constructive logic of pieces of information. The focus is on the definition of a data model suitable for organizing the information stored in OO systems. The underlying constructive logic supports a correct way of storing, exchanging and elaborating information.