VSL 2014: VIENNA SUMMER OF LOGIC 2014
PAAR ON WEDNESDAY, JULY 23RD, 2014

View: session overviewtalk overviewside by side with other conferences

08:45-10:15 Session 159D: Superposition I
Location: FH, Hörsaal 7
08:45
A Deductive-Complete Constrained Superposition Calculus for Ground Flat Equational Clauses

ABSTRACT. We describe an algorithm that generates prime implicates of equational clause sets without variables and function symbols. The procedure is based on constrained superposition rules, where constraints are used to store literals that are asserted as additional axioms (or hypotheses) during the proof search. This approach is sound and deductive-complete, and it is more ecient than previous algorithms based on conditional paramodulation. It is also more exible in the sense that it allows one to restrict the search space by imposing additional properties that the generated implicates should satisfy (e.g., to ensure relevance).

09:15
Invited talk: Hierarchic Superposition Revisited
SPEAKER: Uwe Waldmann

ABSTRACT. In 1994, Bachmair, Ganzinger, and Waldmann introduced the hierarchical superposition calculus as a generalization of the superposition calculus for black-box style theory reasoning. Their calculus works in a framework of hierarchic specifications. It tries to prove the unsatisfiability of a set of clauses with respect to interpretations that extend a background model such as the integers with linear arithmetic conservatively, that is, without identifying distinct elements of old sorts ("confusion") and without adding new elements to old sorts ("junk"). We show how the calculus can be improved, report on practical experiments, and present a new completeness result for non-compact classes of background models (i.e., linear integer or rational arithmetic restricted to standard models).

10:15-10:45Coffee Break
10:45-13:00 Session 166I: Meta-methods for theorem proving
Location: FH, Hörsaal 7
10:45
Automated Theorem Proving using the TPTP Process Instruction Language

ABSTRACT. The TPTP (Thousands of Problems for Theorem Provers) World is a well established infrastructure for Automated Theorem Proving (ATP). In the context of the TPTP World, the TPTP Process Instruction (TPI) language provides capabilities to input, output and organize logical formulae, and control the execution of ATP systems. This paper reviews the TPI language, describes a shell interpreter for the language, and demonstrates their use in theorem proving.

11:15
The Efficiency of Automated Theorem Proving by Translation to Less Expressive Logics

ABSTRACT. Many Automated Theorem Prover (ATP) systems for different logics, and translators for translating different logics from one to another, have been developed and are now available. Some logics are more expressive than others, and it is easier to express problems in those logics. On the other hand, the ATP systems for less expressive logics have been under development for many years, and are more powerful and reliable. There is a trade-off between expressivity of a logic, and the power and reliability of the available ATP systems. Translators and ATP systems can be combined to try to solve a problem. In this research, an experiment has been carried out to compare the performance of difference combinations of translators and ATP systems.

11:45
Machine Learner for Automated Reasoning 0.4 and 0.5
SPEAKER: Josef Urban

ABSTRACT. Machine Learner for Automated Reasoning (MaLARea) is a learning and reasoning system for proving in large formal libraries where thousands of theorems are available when attacking a new conjecture, and a large number of related problems and proofs can be used to learn specific theorem-proving knowledge. The last version of the system has by a large margin won the 2013 CASC LTB competition. This paper describes the motivation behind the methods used in MaLARea, discusses the general approach and the issues arising in evaluation of such system, and describes the Mizar@Turing100 and CASC'24 versions of MaLARea.

12:15
BliStr: The Blind Strategymaker
SPEAKER: Josef Urban

ABSTRACT. BliStr is a system that automatically develops strong targetted theorem-proving strategies for the E prover on a large set of diverse problems. The main idea is to interleave (i) iterated low-timelimit local search for new strategies on small sets of similar easy problems with (ii) higher-timelimit evaluation of the new strategies on all problems. The accumulated results of the global higher-timelimit runs are used to define and evolve the notion of "similar easy problems'", and to control the evolution of the next strategy. The technique significantly strengthened the set of E strategies used by the MaLARea, E-MaLeS, and E systems in the CASC@Turing 2012 competition, particularly in the Mizar division. Similar improvement was obtained on the problems created from the Flyspeck corpus.

13:00-14:30Lunch Break
14:30-16:00 Session 172H: Superposition II
Location: FH, Hörsaal 7
14:30
A Model Guided Instantiation Heuristic for the Superposition Calculus with Theories
SPEAKER: Joshua Bax

ABSTRACT. Generalised Model Finding (GMF) is a quantifier instantiation heuristic for the superposition calculus in the presence of interpreted theories with arbitrarily quantified free function symbols ranging into theory sorts. The free function symbols are approximated by finite partial function graphs along with some simplifying assumptions which are iteratively refined. Here we present an outline of the GMF approach, give an improvement that addresses some of these and then present some ideas for extending it with concepts from instantiation based theorem proving.

15:00
Logtk : A Logic ToolKit for Automated Reasoning and its Implementation
SPEAKER: Simon Cruanes

ABSTRACT. We describe the design and implementation of Logtk, an OCaml library for writing automated reasoning tools that deal with (possibly typed) first-order logic. The library provides data structures and algorithms to represent terms, formulas, substitutions, perform unification, index terms, parse problems, as well as a few tools to demonstrate itsuse. It is the basis of a full-fledged superposition prover.

15:30
Polymorphic+Typeclass Superposition
SPEAKER: Daniel Wand

ABSTRACT. We present an extension of superposition that natively handles a polymorphic type system extended with type classes, thus eliminating the need for type encodings when used by an interactive theorem prover like Isabelle/HOL. We describe syntax, typing rules, semantics, the polymorphic superposition calculus and an evaluation on a problem set that is generated from Isabelle/HOL theories. Our evaluation shows that native polymorphic+typeclass performance compares favorably to monomorphisation, a highly efficient but incomplete way of dealing with polymorphism.

16:00-16:30Coffee Break
16:30-18:00 Session 175J: Proving and Disproving
Location: FH, Hörsaal 7
16:30
Beagle as a HOL4 external ATP method

ABSTRACT. This paper presents BEAGLE TAC, a HOL4 tactic for using Beagle as an external ATP for discharging HOL4 goals. We implement a translation of the higher-order goals to the TFA format of TPTP and add trace output to Beagle to reconstruct the intermediate steps derived by the ATP in HOL4. Our translation combines the characteristics of existing successful translations from HOL to FOL and SMT-LIB, however we needed to adapt certain stages of the translation in order to benefit form the expressivity of the TFA format and the power of Beagle. In our initial experiments, we demonstrate that our system can prove, without any arithmetic lemmas, 81% of the goals solved by Metis.

17:00
Razor: Provenance and Exploration in Model-Finding

ABSTRACT. Razor is a model-finder for first-order theories presented in geometric form;  geometric logic is a variant of first-order logic that focuses on "observable'' properties. An important guiding principle of Razor is that it be accessible to users who are not necessarily expert in formal methods;  application areas include software design, analysis of security protocols and policies, and configuration management.
 
A core functionality of the tool is that it supports exploration of the space of models of a given input theory, as well as presentation of provenance information about the elements and facts of a model.   The crucial mathematical tool is the ordering relation on models determined by homomorphism, and Razor prefers models that are minimal with respect to this homomorphism-ordering.

17:30
SGGS Theorem Proving: an Exposition

ABSTRACT. We present in expository style the main ideas in SGGS, which stands for Semantically-Guided Goal-Sensitive theorem proving. SGGS uses sequences of constrained clauses to represent models, instance generation to go from a candidate model to the next, and resolution as well as other inferences to repair the model. SGGS is refutationally complete for first-order logic, model based, semantically guided, proof confluent, and goal sensitive, which appears to be a rare combination of features. In this paper we describe the core of SGGS in a narrative style, emphasizing ideas and trying to keep technicalities to a minimum, in order to advertise it to builders and users of theorem provers.