UITP 2016

We are really pleased to have a paper on our work on diagrammatic tactics accepted at UITP 2016, which is an IJCAR workshop. Sven will be giving a talk and demo at the workshop. The paper is called Tactical Diagrammatic Reasoning, and here’s the abstract:

Although automated reasoning with diagrams has been possible for some years, tools for diagrammatic reasoning are generally much less sophisticated than their sentential cousins. The tasks of exploring levels of automation and abstraction in the construction of proofs and of providing explanations of solutions expressed in the proofs remain to be addressed. In this paper we take an interactive proof assistant for Euler diagrams, Speedith, and add tactics to its
reasoning engine, providing a level of automation in the construction of proofs. By adding tactics to Speedith’s repertoire of inferences, we ease the interaction between the user and the system and capture a higher level explanation of the essence of the proof. We analysed the design options for tactics by using metrics which relate to human readability, such as the number of inferences and the amount of clutter present in diagrams. Thus, in contrast to the normal case with sentential tactics, our tactics are designed to not only prove the theorem, but also to support explanation.

Speedith

You will find a zip file containing the 2016 version of Speedith at the following link:

speedith-2016

Extract the archive. This will create the Speedith executable, speedith.jar and a folder with examples.

 

Please follow these instructions:

To use Speedith with Euler diagrams, please open the Preferences
(File->Preferences) on the first Startup.

  1. Tab Diagram Type: Choose Euler Diagrams
  2. Tab Tactics: Check Show low level-tactics if you want to see/apply all
    possible tactics provided by Speedith. Otherwise, only the high-level
    tactics (Venn (Depth), Venn (Breadth) and Copy Shading and Contours) will
    be available.
  3. Tab Auto Prover: Check that the automatic proof search in the background
    is switched of. The implementation of the automatic prover is only a prototype and tends to use up all memory that is available.

 

Examples of both proofs and proof goals are contained in the examples folder. The subfolder paper contains all proofs and proof goals mentioned in the submission to UITP 2016.

 

Requirements: Java 7

(Speedith has not been tested with Java 8. It might work or it might not.)

 

This version of Speedith has been compiled and tested on Ubuntu 16.04 (LTS). It should work on MacOS and Windows as long as a Java Runtime Environment is present, but we cannot give any guarantees.

Introducing the project

The aim of this project is to develop an understanding of what makes one diagrammatic proof more “readable” than another, and to apply that understanding in diagrammatic tools.

To begin unpacking that last sentence, whenever we use the word “readable” we ought to explain what we mean by it. Readability is, in general, a subjective quality and a matter of taste of course. I think you’d be right to be deeply sceptical of an algorithm to identify readability in fiction, for instance. Fortunately, we’re talking about formal proofs, where each step of the proof is generated from the ones that went before it according to a limited set of proof rules. For each (true) theorem, there are infinitely many proofs, each of them formally equivalent. From among those proofs, we want to find ones which users find easier to understand and there are some straightforward ways in which that can be measured — for instance, we could say that one proof, P, is more readable than another, Q, if users can identify which rules are applied in each step in P, but they are less able to do that for Q. The length of time it takes a user to read and understand a proof is part of readability too.

There is a rich history of logical diagrams, reaching back to Leibniz. In recent years, there has been a lot of interest in logical diagrams as a way to enable non-logicians to make precise statements, for instance when producing conceptual models such as ontologies. Our project focusses on Euler diagrams because they are well-known and many people find them easy to understand. This is the kind of theorem you can state and prove using Euler diagrams:

 

g4313

Euler diagrams themselves aren’t expressive enough for conceptual modelling tasks but more expressive systems that extend Euler diagrams software exist, such as spider diagrams and concept diagrams. So, if we can understand readability in Euler diagrams, we have a good chance of understanding it in systems that are expressive enough for real-world tasks too.

Another good reason to choose Euler diagrams is that there are already software reasoning tools, or theorem provers, that work with them. Theorem provers are either automated (enter a theorem and the tool generates a proof, if one exists) or interactive (enter the theorem then choose which rule or tactic should be applied next). EDITH is an automated Euler diagram theorem prover developed by our colleagues Gem Stapleton, Jean Flower and others at the Visual Modelling Group. Speedith, an interactive spider diagram prover, is a descendant of EDITH. We are planning to produce a version of Speedith that, like its predecessor, works automatically and do generates proofs with readability and the human reader in mind. We’re calling it Readith 🙂