Using DAG transformations to verify Euler/Venn homogeneous and Euler/Venn FOL heterogeneous rules of inference

In this paper we will present a graph-transformation based method for the verification of heterogeneous first order logic (FOL) and Euler/Venn proofs. In previous work, it has been shown that a special collection of directed acyclic graphs (DAGs) can be used interchangeably with Euler/Venn diagrams in reasoning processes. Thus, proofs which include Euler/Venn diagrams can be thought of as proofs with DAGs where steps involving only Euler/Venn diagrams can be treated as particular DAG transformations. Here we will show how the characterization of these manipulations can be used to verify Euler/Venn proofs. Also, a method for verifying the use of heterogeneous Euler/Venn and FOL reasoning rules will be presented that is also based upon DAG transformations .     

Nesting in Euler Diagrams: syntax,semantics and construction

This paper considers the notion of nesting in Euler diagrams, and how nesting affects the interpretation and construction of such diagrams. After setting up the necessary definitions for concrete Euler diagrams (drawn in the plane) and abstract diagrams (having just formal structure), the notion of nestedness is defined at both concrete and abstract levels. The concept of a dual graph is used to give an alternative condition for a drawable abstract Euler diagram to be nested. The natural progression to the diagram semantics is explored and we present a nested form for diagram semantics. We describe how this work supports tool-building for diagrams, and how effective we might expect this support to be in terms of the proportion of nested diagrams.     

Automated Theorem Proving in Euler Diagram Systems

Diagrammatic reasoning has the potential to be important in numerous application areas. This paper focuses on the simple, but widely used, Euler diagrams that form the basis of many more expressive logics. We have implemented a diagrammatic theorem prover, called Edith, which has access to four sound and complete sets of reasoning rules for Euler diagrams. Furthermore, for each rule set we develop a sophisticated heuristic to guide the search for a proof. This paper is about understanding how the choice of reasoning rule set affects the time taken to find proofs. Such an understanding will influence reasoning rule design in other logics. Moreover, this work specific to Euler diagrams directly benefits the many logics based on Euler diagrams. We investigate how the time taken to find a proof depends not only on the proof task but also on the reasoning system used. Our evaluation allows us to predict the best choice of reasoning system, given a proof task, in terms of time taken, and we extract a guide for defining reasoning rules for other logics in order to minimize time requirements.     

Theories of Diagrammatic Reasoning: Distinguishing Component Problems

Theories of diagrams and diagrammatic reasoning typically seek to account for either the formal semantics of diagrams, or for the advantages which diagrammatic representations hold for the reasoner over other forms of representation. Regrettably, almost no theory exists which accounts for both of these issues together, nor how they affect one another. We do not attempt to provide such an account here. We do, however, seek to lay out larger context than is generally used for examining the processes of using diagrams in reasoning or communication. A context in which detailed studies of sub-problems, such as the formal semantics or cognitive impact of specific diagrammatic systems, may be embedded.Accounts of the embedding of sentential logics in the computational processes of reasoners and communicators are relatively well developed from several decades of research in AI. Analogies between the sentential and the graphical cases are quite revealing about both similarities and differences. To provide a structure for the 'grand context' of diagrammatic representation and reasoning, and to clarify the relations between its component problems, we examine carefully these analogies and the decomposition they provide of subproblems for analysing diagrammatic reasoning.     

Investigating Reasoning with Constraint Diagrams

Constraint diagrams are a visual notation designed to express logical constraints. Augmenting the diagrams with a reading tree (effectively a partial ordering of quantifiers) ensures that each diagram has a unique semantic interpretation.In this paper, we discuss examples of reasoning rules for augmented constraint diagrams which exhibit interesting properties or difficulties that can arise when developing rules for such a diagrammatic system. We do not present a complete set of rules, but investigate the generic problems arising, providing solutions. One problem corresponds to the nesting of quantifiers and another relates to the domain of universal quantification. These issues may be an important consideration in the definition of other logical reasoning systems which explicitly represent quantification diagrammatically.     

A general method for drawing area-proportional Euler diagrams

Area-proportional Euler diagrams have many applications, for example they are often used for visualizing data in medical and biological domains. There have been a number of recent research efforts to automatically draw Euler diagrams when the areas of the regions are not considered, leading to a range of different drawing techniques. By contrast, substantially less progress has been made on the problem of automatically drawing area-proportional Euler diagrams, although some partial results have been derived. In this paper, we considerably advance the state-of-the-art in area-proportional Euler diagram drawing by presenting the first method that is capable of generating such a diagram given any area-proportional specification. Moreover, our drawing method is sufficiently flexible that it allows one to specify which of the typically enforced well-formedness conditions should be possessed by the to-be-drawn Euler diagram.     

Robbins algebra: Conditions that make a near-boolean algebra boolean

Some problems posed years ago remain challenging today. In particular, the Robbins problem, which is still open and which is the focus of attention in this paper, offers interesting challenges for attack with the assistance of an automated reasoning program; for the study presented here, we used the program OTTER. For example, when one submits this problem, which asks for a proof that every Robbins algebra is a Boolean algebra, a large number of deduced clauses results. One must, therefore, consider the possibility that there exists a Robbins algebra that is not Boolean; such an algebra would have to be infinite. One can instead search for properties that, if adjoined to those of a Robbins algebra, guarantee that the algebra is Boolean. Here we present a number of such properties, and we show how an automated reasoning program was used to obtain the corresponding proofs. Additional properties have been identified, and we include here examples of using such a program to check that the corresponding hand-proofs are correct. We present the appropriate input for many of the examples and also include the resulting proofs in clause notation.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Rough 3-valued algebras

Rough set theory is an important tool for dealing with granularity and vagueness in information systems. This paper studies a kind of rough set algebra. The collection of all the rough sets of an approximation space can be made into a 3-valued Lukasiewicz algebra. We call the algebra a rough 3-valued Lukasiewicz algebra. In this paper, we focus on the rough 3-valued Lukasiewicz algebras, which are a special kind of 3-valued Lukasiewicz algebras. Firstly, we examine whether the rough 3-valued Lukasiewicz algebra is an axled 3-valued Lukasiewicz algebra. Secondly, we present the condition under which the rough 3-valued Lukasiewicz algebra is also a 3-valued Post algebra. Then we investigate the 3-valued Post subalgebra problem of the rough 3-valued Lukasiewicz algebra. Finally, this paper studies the relationship between the rough 3-valued Lukasiewicz algebra and the Boolean algebra constructed by all the exact sets of the corresponding approximation space.     

Automating the Search for Elegant Proofs

The research reported in this article was spawned by a colleague's request to find an elegant proof (of a theorem from Boolean algebra) to replace his proof consisting of 816 deduced steps. The request was met by finding a proof consisting of 100 deduced steps. The methodology used to obtain the far shorter proof is presented in detail through a sequence of experiments. Although clearly not an algorithm, the methodology is sufficiently general to enable its use for seeking elegant proofs regardless of the domain of study. In addition to (usually) being more elegant, shorter proofs often provide the needed path to constructing a more efficient circuit, a more effective algorithm, and the like. The methodology relies heavily on the assistance of McCune's automated reasoning program OTTER. Of the aspects of proof elegance, the main focus here is on proof length, with brief attention paid to the type of term present, the number of variables required, and the complexity of deduced steps. The methodology is iterative, relying heavily on the use of three strategies: the resonance strategy, the hot list strategy, and McCune's ratio strategy. These strategies, as well as other features on which the methodology relies, do exhibit tendencies that can be exploited in the search for shorter proofs and for other objectives. To provide some insight regarding the value of the methodology, I discuss its successful application to other problems from Boolean algebra and to problems from lattice theory. Research suggestions and challenges are also offered.     

eulerForce: Force-directed layout for Euler diagrams

Euler diagrams use closed curves to represent sets and their relationships. They facilitate set analysis, as humans tend to perceive distinct regions when closed curves are drawn on a plane. However, current automatic methods often produce diagrams with irregular, non-smooth curves that are not easily distinguishable. Other methods restrict the shape of the curve to for instance a circle, but such methods cannot draw an Euler diagram with exactly the required curve intersections for any set relations. In this paper, we present eulerForce, as the first method to adopt a force-directed approach to improve the layout and the curves of Euler diagrams generated by current methods. The layouts are improved in quick time. Our evaluation of eulerForce indicates the benefits of a force-directed approach to generate comprehensible Euler diagrams for any set relations in relatively fast time.     

Representing short-term observations of moving objects by a simple visual language

In a variety of dynamical systems, formations of motion patterns occur. Observing colonies of animals, for instance, for the scientist it is not only of interest which kinds of formations these animals show, but also how they altogether move around. In order to analyse motion patterns for the purpose of making predictions, to describe the behaviour of systems, or to index databases of moving objects, methods are required for dealing with them. This becomes increasingly important since a number of technologies have been devised which allow objects precisely to get traced. However, the indeterminacy of spatial information in real world environments also requires techniques to approximate reasoning, for example, in order to compensate for small and unimportant distinctions which are due to noisy measurements. As a consequence, precise as well as coarse motion patterns have to be dealt with.A set of 16 atomic motion patterns is proposed. On the one hand, a relation algebra is defined on them. On the other hand, these 16 relations form the basis of a visual language using which motion patterns can easily be dealt with in a diagrammatic way. The relations are coarse but crisp and they allow imprecise knowledge about motion patterns to be dealt with, while their diagrammatic realisation also allow precise patterns to get handled. While almost all approaches consider motion patterns along arbitrary time intervals, this paper in particular focuses on short-term motion patterns as we permanently observe them in our everyday life.The bottom line of the current work, however, is yet more general. While it has been widely argued that it makes sense to use both sentential and diagrammatic representations in order to represent different things in the same system adequately (and hence differently), we argue that it makes even sense to represent the same things differently in order to grasp different aspects of one and the same object of interest from different viewpoints. We demonstrate this by providing both a sentential and a diagrammatic representation for the purpose of grasping different aspects of motion patterns. It shows that both representations complement each other.     

Boolean Algebra as a Fragment of the Theory of Boolean Toposes

Basic identities of Boolean algebra are considered, and their categorical analogs are proved.     

On the expressiveness of second-order spider diagrams

Existing diagrammatic notations based on Euler diagrams are mostly limited in expressiveness to monadic first-order logic with an order predicate. The most expressive monadic diagrammatic notation is known as spider diagrams of order. A primary contribution of this paper is to develop and formalise a second-order diagrammatic logic, called second-order spider diagrams, extending spider diagrams of order. A motivation for this lies in the limited expressiveness of first-order logics. They are incapable of defining a variety of common properties, like ‘is even’, which are second-order definable. We show that second-order spider diagrams are at least as expressive as monadic second-order logic. This result is proved by giving a method for constructing a second-order spider diagram for any regular expression. Since monadic second-order logic sentences and regular expressions are equivalent in expressive power, this shows second-order spider diagrams can express any sentence of monadic second-order logic.     

A Representation Theorem for MV-algebras

An MV-pair is a pair (B,G) where B is a Boolean algebra and G is a subgroup of the automorphism group of B satisfying certain conditions. Let ~ _G be the equivalence relation on B naturally associated with G. We prove that for every MV-pair (B,G), the effect algebra B/ ~ _G is an MV-effect algebra. Moreover, for every MV-effect algebra M there is an MV-pair (B,G) such that M is isomorphic to B/ ~ _G . This research is supported by grant VEGA G-1/3025/06 of MŠ SR, Slovakia and by the Science and Technology Assistance Agency under the contract No. APVT-51-032002.     

A normal form for spider diagrams of order

We develop a reasoning system for an Euler diagram based visual logic, called spider diagrams of order. We define a normal form for spider diagrams of order and provide an algorithm, based on the reasoning system, for producing diagrams in our normal form. Normal forms for visual logics have been shown to assist in proving completeness of associated reasoning systems. We wish to use the reasoning system to allow future direct comparison of spider diagrams of order and linear temporal logic.     

Free binary decision diagrams for the computation of EAR n

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional to binary decision diagram) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined for n × n Boolean matrices: EAR_n(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EAR_n has size at least and we present a construction of such diagrams of size approximately .