Dissertations / Theses on the topic 'Theorem proving'
To see the other types of publications on this topic, follow the link: Theorem proving.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Theorem proving.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Ballarin, Clemens Michael. "Computer algebra and theorem proving." Thesis, University of Cambridge, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.624429.
Full text
2
Ji, Kailiang. "Model checking and theorem proving." Sorbonne Paris Cité, 2015. http://www.theses.fr/2015USPCC250.
Full textAbstract:
Le model checking est une technique de vérification automatique de propriétés de correction de systèmes finis. Normalement, les outils de model checking ont deux caractéristiques remarquables : ils sont automatisés et ils produisent un contre-exemple si le système ne satisfait pas la propriété. La Déduction Modulo est une reformulation de la logique des prédicats où certains axiomes---possiblement tous---sont remplacés par des règles de réécriture. Le but de cette dissertation est de donner un encodage de propriétés temporelles exprimées en CTL en des formules du premier ordre, en exprimant l'équivalence logique entre les opérateurs temporels avec des règles de réécriture. De cette manière, les algorithmes de recherche de preuve conçus pour la Déduction Modulo, tels que la Résolution Modulo ou les Tableaux Modulo, peuvent être utilisés pour vérifier des propriétés temporelles de systèmes de transition finis. Afin d'accomplir le but de résoudre des problèmes de model checking avec un prouveur automatique quelconque, trois travaux sont inclus dans cette dissertation. Premièrement, nous abordons le problème de parcours de graphes en model checking avec des prouveurs automatiques. Nous proposons une façon d'encoder un graphe en tant que formule de manière à ce que le parcours du graphe correspond aux étapes de résolution. Nous présentons ensuite comment formuler les problèmes de model checking comme des formules du premier ordre en Déduction Modulo. La correction et la complétude de notre méthode montre que résoudre des problèmes de model checking CTL avec des prouveurs automatiques est faisable. Enfin, en nous appuyant sur la base théorique du deuxième travail, nous proposons une méthode de model checking symbolique. Cette méthode est implantée dans iProver Modulo, qui est un prouveur automatique du premier ordre qui utilise la Résolution Modulo PolariséeModel checking is a technique for automatically verifying correctness properties of finite systems. Normally, model checking tools enjoy two remarkable features: they are fully automatic and a counterexample will be produced if the system fails to satisfy the property. . Deduction Modulo is a reformulation of Predicate Logic where some axioms- - - possibly ail---are replaced by rewrite rules. The focus of this dissertation is to give an encoding of temporal properties expressed in CTL as first -order formulas, by translating the logical equivalence between temporal operators into rewrite rules. This way, proof -search algorithms designed for Deduction Modulo, such as Resolution Modulo or Tableaux Modulo, can be used to verify temporal properties of finite transition systems. To achieve the aim of solving model checking problems with an off-the-shelf automated theorem proyer, three works are included in this dissertation. First, we address the graph traversai problems in model checking with automated theorem provers. As a preparation work, we propose a way of encoding a graph as a formula such that the traversal of the graph corresponds to resolution steps. Then we present the way of translating model checking problems as proving first-order formulas in Deduction Modulo. The soundness and completeness of our method shows that solving CTL model checking problems with automated theorem provers is feasible. At last, based on the theoretical basis in the second work, we propose a symbolic model checking method. This method is implemented in iProver Modulo, which is a first-order theorem proyer uses Polarized Resolution Modulo
3
Kakkad, Aman. "Machine Learning for Automated Theorem Proving." Scholarly Repository, 2009. http://scholarlyrepository.miami.edu/oa_theses/223.
Full textAbstract:
Developing logic in machines has always been an area of concern for scientists. Automated Theorem Proving is a field that has implemented the concept of logical consequence to a certain level. However, if the number of available axioms is very large then the probability of getting a proof for a conjecture in a reasonable time limit can be very small. This is where the ability to learn from previously proved theorems comes into play. If we see in our own lives, whenever a new situation S(NEW) is encountered we try to recollect all old scenarios S(OLD) in our neural system similar to the new one. Based on them we then try to find a solution for S(NEW) with the help of all related facts F(OLD) to S(OLD). Similar is the concept in this research. The thesis deals with developing a solution and finally implementing it in a tool that tries to prove a failed conjecture (a problem that the ATP system failed to prove) by extracting a sufficient set of axioms (we call it Refined Axiom Set (RAS)) from a large pool of available axioms. The process is carried out by measuring the similarity of a failed conjecture with solved theorems (already proved) of the same domain. We call it "process1", which is based on syntactic selection of axioms. After process1, RAS may still have irrelevant axioms, which motivated us to apply semantic selection approach on RAS so as to refine it to a much finer level. We call this approach as "process2". We then try to prove failed conjecture either from the output of process1 or process2, depending upon whichever approach is selected by the user. As for our testing result domain, we picked all FOF problems from the TPTP problem domain called SWC, which consisted of 24 broken conjectures (problems for which the ATP system is able to show that proof exists but not able to find it because of limited resources), 124 failed conjectures and 274 solved theorems. The results are produced by keeping in account both the broken and failed problems. The percentage of broken conjectures being solved with respect to the failed conjectures is obviously higher and the tool has shown a success of 100 % on the broken set and 19.5 % on the failed ones.
4
Folkler, Andreas. "Automated Theorem Proving : Resolution vs. Tableaux." Thesis, Blekinge Tekniska Högskola, Institutionen för programvaruteknik och datavetenskap, 2002. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-5531.
Full textAbstract:
The purpose of this master thesis was to investigate which of the two methods, resolution and tableaux, that is the most appropriate for automated theorem proving. This was done by implementing an automated theorem prover, comparing and documenting implementation problems, and measuring proving efficiency. In this thesis, I conclude that the resolution method might be more suitable for an automated theorem prover than tableaux, in the aspect of ease of implementation. Regarding the efficiency, the test results indicate that resolution is the better choice.Syftet med detta magisterarbete var att undersöka vilken av de två metoderna, resolution och tablå, som är mest lämpad för automatisk teorembevisning. Detta gjordes genom att implementera en automatisk teorembevisare, jämföra och dokumentera problem, samt att mäta prestanda för bevisning. I detta arbete drar jag slutsatsen att resolutionsmetoden förmodligen är mer lämpad än tablåmetoden för en automatisk teorembevisare, med avseende på hur svår den är att implementera. När det gäller prestanda indikerar utförda tester att resolutionsmetoden är det bästa valet.
5
Amjad, Hasan. "Combining model checking and theorem proving." Thesis, University of Cambridge, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.616074.
Full text
6
Bridge, J. P. "Machine learning and automated theorem proving." Thesis, University of Cambridge, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.596901.
Full textAbstract:
Computer programs to find formal proofs of theorems were originally designed as tools for mathematicians, but modern applications are much more diverse. In particular they are used in formal methods to verify software and hardware designs to prevent errors being introduced into systems. Despite this, the high level of human expertise required in their use means that theorem proving tools are not widely used by non-specialists. The work described in this dissertation addresses one aspect of this problem, that of heuristic selection. In theory theorem provers should be automatic; in practice the heuristics used in the proof search are not universally optimal for all problems so human expertise is required to determie heuristic choice and to set parameter values. Modern machine learning has been applied to the automation of heuristic selection in a first order logic theorem prover. One objective was to find if there are any features of a proof problem that are both easy to measure and provide useful information for determining heuristic choice. Another was to determine and demonstrate a practical approach to making theorem provers truly automatic. In the experimental work, heuristic selection based on features of the conjecture to be proved and the associated axioms is shown to do better than any single heuristic. Additionally a comparison has been made between static features, measured prior to the proof search process, and dynamic features that measure changes arising in the early stages of proof search. Further work was done on determining which features are important, demonstrating that good results are obtained with only a few features required.
7
Hou, Tie. "Interactive theorem proving and program extraction." Thesis, Swansea University, 2014. https://cronfa.swan.ac.uk/Record/cronfa42845.
Full text
8
Syme, Donald Robert. "Declarative theorem proving for operational semantics." Thesis, University of Cambridge, 1999. https://www.repository.cam.ac.uk/handle/1810/252967.
Full textAbstract:
This dissertation is concerned with techniques for formally checking properties of systems that are described by operational semantics. We describe innovations and tools for tackling this problem, and a large case study in the application of these tools. The innovations centre on the notion of "declarative theorem proving", and in particular techniques for declarative proof description. We define what we mean by this, assess its costs and benefits, and describe the impact of this approach with respect to four fundamental areas of theorem prover design: specification, proof description, automated reasoning and interaction. We have implemented our techniques as the DECLARE system, which we use to demonstrate how our principles translate into practice. With regard to specification we briefly describe the range of specification devices employed, and present a technique for validating operational specifications against their informal requirements. The proof language is based on just three major devices: decomposition, justification by automation and second order schema application, and we describe these in detail. We also specify the requirements for an automated reasoning engine in the context of declarative proof and operational semantics. We describe the engine we have implemented and assess how it does and does not meet these requirements. The case study is a formally checked proof of the type soundness of a subset of the Java language, and is an interesting result in its own right. We define an operational semantics for this subset, based on Drossopoulou and Eisenbach's work in this field, and then outline the structure of our type soundness proot which is based on a notion of conformance. Some errors in the Java Language Specification and Drossopoulou and Eisenbach's work were discovered during this process, and these are described. Finally, we argue why declarative techniques substantially improved the quality of the results achieved, particularly with respect to maintainability and readability.
9
Harrison, John Robert. "Theorem proving with the real numbers." Thesis, University of Cambridge, 1996. https://www.repository.cam.ac.uk/handle/1810/265488.
Full textAbstract:
This thesis discusses the use of the real numbers in theorem proving. Typically, theorem provers only support a few 'discrete' datatypes such as the natural numbers. However the availability of the real numbers opens up many interesting and important application areas, such as the verification of floating point hardware and hybrid systems. It also allows the formalization of many more branches of classical mathematics, which is particularly relevant for attempts to inject more rigour into computer algebra systems. Our work is conducted in a version of the HOL theorem prover. We describe the rigorous definitional construction of the real numbers, using a new version of Cantor's method, and the formalization of a significant portion of real analysis. We also describe . an advanced derived decision procedure for the 'Tarski subset' of real algebra as well as some more modest but practically useful tools for automating explicit calculations and routine linear arithmetic reasoning. Finally, we consider in more detail two interesting application areas. We discuss the desirability of combining the rigour of theorem provers with the power and convenience of computer algebra systems, and explain a method we have used in practice to achieve this. We then move on to the verification of floating point hardware. After a careful discussion of possible correctness specifications, we report on two case studies, one involving a transcendental function. We aim to show that a theory of real numbers is useful in practice and interesting in theory, and that the 'LCF style' of theorem proving is well suited to the kind of work we describe. As for verification applications, we hope to convince the reader that the verification of real industrial designs is well within the abilities of current theorem proving .technology.
10
Haufe, Sebastian. "Automated Theorem Proving for General Game Playing." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-89998.
Full textAbstract:
While automated game playing systems like Deep Blue perform excellent within their domain, handling a different game or even a slight change of rules is impossible without intervention of the programmer. Considered a great challenge for Artificial Intelligence, General Game Playing is concerned with the development of techniques that enable computer programs to play arbitrary, possibly unknown n-player games given nothing but the game rules in a tailor-made description language. A key to success in this endeavour is the ability to reliably extract hidden game-specific features from a given game description automatically. An informed general game player can efficiently play a game by exploiting structural game properties to choose the currently most appropriate algorithm, to construct a suited heuristic, or to apply techniques that reduce the search space. In addition, an automated method for property extraction can provide valuable assistance for the discovery of specification bugs during game design by providing information about the mechanics of the currently specified game description. The recent extension of the description language to games with incomplete information and elements of chance further induces the need for the detection of game properties involving player knowledge in several stages of the game.
In this thesis, we develop a formal proof method for the automatic acquisition of rich game-specific invariance properties. To this end, we first introduce a simple yet expressive property description language to address knowledge-free game properties which may involve arbitrary finite sequences of successive game states. We specify a semantic based on state transition systems over the Game Description Language, and develop a provably correct formal theory which allows to show the validity of game properties with respect to their semantic across all reachable game states. Our proof theory does not require to visit every single reachable state. Instead, it applies an induction principle on the game rules based on the generation of answer set programs, allowing to apply any off-the-shelf answer set solver to practically verify invariance properties even in complex games whose state space cannot totally be explored. To account for the recent extension of the description language to games with incomplete information and elements of chance, we correctly extend our induction method to properties involving player knowledge. With an extensive evaluation we show its practical applicability even in complex games.
11
Kim, Choon Kyu 1963. "Parallel semantic tree theorem proving with resolutions." Thesis, McGill University, 2004. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=85076.
Full textAbstract:
Semantic trees have often been used as theoretical tools for showing the unsatisfiability of clauses in first-order predicate logic. Their practicality has been overshadowed, however, by other strategies though considerable effort has been made to improve semantic tree theorem provers over the last decade.In this thesis, we propose building a parallel system through the integration of semantic trees with resolution-refutation. The proposal comes from the observations that the appropriate strategy for one class of theorems is often very different from that for another class and many semantic trees tend to be linear. In the linear semantic tree, one of the two branches from each node leads to a failure node. Such linearity is attractive because we can focus our efforts on closing the remaining branch. Unfortunately, the strategy of building a closed linear semantic tree is incomplete. To help to achieve closure, we introduce the use of unit clauses derived from resolutions when necessary, leading to a strategy that combines the construction of semantic trees with resolution-refutation.
The parallel semantic tree theorem prover, called PrHERBY, utilizes dedicated resolutions in scalable manner and strategically selects atoms to construct semantic trees. In addition, a parallel grounding scheme allows each system to have its own instance of generated atoms, thereby increasing the possibility of success. The PrHERBY system presented performs significantly better and generally finds proof using fewer atoms than the semantic tree prover, HERBY and its parallel version, PHERBY.
12
Sadri, Fariba. "A theorem-proving approach to database integrity." Thesis, Imperial College London, 1988. http://hdl.handle.net/10044/1/47238.
Full text
13
Ne, Win Toh 1979. "Theorem-proving distributed algorithms with dynamic analysis." Thesis, Massachusetts Institute of Technology, 2003. http://hdl.handle.net/1721.1/29702.
Full textAbstract:
Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.Includes bibliographical references (p. 185-194).
Theorem provers are notoriously hard to use because of the amount of human interaction they require, but they are important tools that can verify infinite state distributed systems. We present a method to make theorem-proving safety properties of distributed algorithms more productive by reducing human intervention. We model the algorithms as I/O automata, render the automata executable, and analyze the test executions with dynamic invariant detection. The human work in using a theorem prover is reduced because our technique provides two forms of assistance: lemmas generated by the dynamic invariant detection for use in the prover; and prover scripts, or tactics, generated from our experience with the I/O automaton model and the knowledge embedded in the test suite used for execution. We test our technique on three case studies: the Peterson 2-process mutual exclusion algorithm, a strong caching implementation of shared memory, and Lamport's Paxos algorithm for distributed consensus. In the development and implementation of our method, we also improved the tools for formal verification of 1/0 automata and for dynamic invariant detection. We describe a new model for specifying I/O automata in the Isabelle theorem prover's logic, and prove the soundness of a technique for verifying invariants in this model in the Isabelle prover. We develop methods for generating proofs of I/0 automata for two theorem provers, the Larch Prover and Isabelle/HOL. We show methods for executing I/O automata for testing, by allowing the execution of some automata defined with universal and existential quantifiers that were previously non-executable. Lastly, we present improvements to dynamic invariant detection in order to make it more scalable - in particular, we show how to achieve efficient incremental dynamic invariant detection, where the detection tool is only allowed to make one pass over its input executions.
by Toh Ne Win.
M.Eng.
14
Martin, Andrew Philip. "Machine-assisted theorem-proving for software engineering." Thesis, University of Oxford, 1994. http://ora.ox.ac.uk/objects/uuid:728d3cee-1dfe-4186-a49f-52b33cbc6551.
Full text
15
Gill, David Michael. "Automatic theorem proving programs and group presentations." Thesis, University of St Andrews, 1995. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.268121.
Full text
16
Zacchiroli, Stefano <1979>. "User interaction widgets for interactive theorem proving." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2007. http://amsdottorato.unibo.it/616/1/Tesi_Zacchiroli.pdf.
Full textAbstract:
Matita (that means pencil in Italian) is a new interactive theorem prover under
development at the University of Bologna. When compared with state-of-the-art
proof assistants, Matita presents both traditional and innovative aspects.
The underlying calculus of the system, namely the Calculus of (Co)Inductive
Constructions (CIC for short), is well-known and is used as the basis of another
mainstream proof assistant—Coq—with which Matita is to some extent compatible.
In the same spirit of several other systems, proof authoring is conducted by the
user as a goal directed proof search, using a script for storing textual commands for
the system. In the tradition of LCF, the proof language of Matita is procedural and
relies on tactic and tacticals to proceed toward proof completion. The interaction
paradigm offered to the user is based on the script management technique at the
basis of the popularity of the Proof General generic interface for interactive theorem
provers: while editing a script the user can move forth the execution point to deliver
commands to the system, or back to retract (or “undo”) past commands.
Matita has been developed from scratch in the past 8 years by several members
of the Helm research group, this thesis author is one of such members. Matita
is now a full-fledged proof assistant with a library of about 1.000 concepts. Several
innovative solutions spun-off from this development effort. This thesis is about the
design and implementation of some of those solutions, in particular those relevant for
the topic of user interaction with theorem provers, and of which this thesis author
was a major contributor. Joint work with other members of the research group
is pointed out where needed. The main topics discussed in this thesis are briefly
summarized below.
Disambiguation. Most activities connected with interactive proving require the
user to input mathematical formulae. Being mathematical notation ambiguous,
parsing formulae typeset as mathematicians like to write down on paper is a challenging
task; a challenge neglected by several theorem provers which usually prefer
to fix an unambiguous input syntax. Exploiting features of the underlying calculus,
Matita offers an efficient disambiguation engine which permit to type formulae in
the familiar mathematical notation.
Step-by-step tacticals. Tacticals are higher-order constructs used in proof scripts
to combine tactics together. With tacticals scripts can be made shorter, readable,
and more resilient to changes. Unfortunately they are de facto incompatible with
state-of-the-art user interfaces based on script management. Such interfaces indeed
do not permit to position the execution point inside complex tacticals, thus introducing
a trade-off between the usefulness of structuring scripts and a tedious big
step execution behavior during script replaying. In Matita we break this trade-off
with tinycals: an alternative to a subset of LCF tacticals which can be evaluated in
a more fine-grained manner.
Extensible yet meaningful notation. Proof assistant users often face the need
of creating new mathematical notation in order to ease the use of new concepts. The
framework used in Matita for dealing with extensible notation both accounts for
high quality bidimensional rendering of formulae (with the expressivity of MathMLPresentation)
and provides meaningful notation, where presentational fragments are
kept synchronized with semantic representation of terms. Using our approach interoperability
with other systems can be achieved at the content level, and direct
manipulation of formulae acting on their rendered forms is possible too.
Publish/subscribe hints. Automation plays an important role in interactive
proving as users like to delegate tedious proving sub-tasks to decision procedures
or external reasoners. Exploiting the Web-friendliness of Matita we experimented
with a broker and a network of web services (called tutors) which can try independently
to complete open sub-goals of a proof, currently being authored in Matita.
The user receives hints from the tutors on how to complete sub-goals and can interactively
or automatically apply them to the current proof.
Another innovative aspect of Matita, only marginally touched by this thesis,
is the embedded content-based search engine Whelp which is exploited to various
ends, from automatic theorem proving to avoiding duplicate work for the user.
We also discuss the (potential) reusability in other systems of the widgets presented
in this thesis and how we envisage the evolution of user interfaces for interactive
theorem provers in the Web 2.0 era.
17
Zacchiroli, Stefano <1979>. "User interaction widgets for interactive theorem proving." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2007. http://amsdottorato.unibo.it/616/.
Full textAbstract:
Matita (that means pencil in Italian) is a new interactive theorem prover under
development at the University of Bologna. When compared with state-of-the-art
proof assistants, Matita presents both traditional and innovative aspects.
The underlying calculus of the system, namely the Calculus of (Co)Inductive
Constructions (CIC for short), is well-known and is used as the basis of another
mainstream proof assistant—Coq—with which Matita is to some extent compatible.
In the same spirit of several other systems, proof authoring is conducted by the
user as a goal directed proof search, using a script for storing textual commands for
the system. In the tradition of LCF, the proof language of Matita is procedural and
relies on tactic and tacticals to proceed toward proof completion. The interaction
paradigm offered to the user is based on the script management technique at the
basis of the popularity of the Proof General generic interface for interactive theorem
provers: while editing a script the user can move forth the execution point to deliver
commands to the system, or back to retract (or “undo”) past commands.
Matita has been developed from scratch in the past 8 years by several members
of the Helm research group, this thesis author is one of such members. Matita
is now a full-fledged proof assistant with a library of about 1.000 concepts. Several
innovative solutions spun-off from this development effort. This thesis is about the
design and implementation of some of those solutions, in particular those relevant for
the topic of user interaction with theorem provers, and of which this thesis author
was a major contributor. Joint work with other members of the research group
is pointed out where needed. The main topics discussed in this thesis are briefly
summarized below.
Disambiguation. Most activities connected with interactive proving require the
user to input mathematical formulae. Being mathematical notation ambiguous,
parsing formulae typeset as mathematicians like to write down on paper is a challenging
task; a challenge neglected by several theorem provers which usually prefer
to fix an unambiguous input syntax. Exploiting features of the underlying calculus,
Matita offers an efficient disambiguation engine which permit to type formulae in
the familiar mathematical notation.
Step-by-step tacticals. Tacticals are higher-order constructs used in proof scripts
to combine tactics together. With tacticals scripts can be made shorter, readable,
and more resilient to changes. Unfortunately they are de facto incompatible with
state-of-the-art user interfaces based on script management. Such interfaces indeed
do not permit to position the execution point inside complex tacticals, thus introducing
a trade-off between the usefulness of structuring scripts and a tedious big
step execution behavior during script replaying. In Matita we break this trade-off
with tinycals: an alternative to a subset of LCF tacticals which can be evaluated in
a more fine-grained manner.
Extensible yet meaningful notation. Proof assistant users often face the need
of creating new mathematical notation in order to ease the use of new concepts. The
framework used in Matita for dealing with extensible notation both accounts for
high quality bidimensional rendering of formulae (with the expressivity of MathMLPresentation)
and provides meaningful notation, where presentational fragments are
kept synchronized with semantic representation of terms. Using our approach interoperability
with other systems can be achieved at the content level, and direct
manipulation of formulae acting on their rendered forms is possible too.
Publish/subscribe hints. Automation plays an important role in interactive
proving as users like to delegate tedious proving sub-tasks to decision procedures
or external reasoners. Exploiting the Web-friendliness of Matita we experimented
with a broker and a network of web services (called tutors) which can try independently
to complete open sub-goals of a proof, currently being authored in Matita.
The user receives hints from the tutors on how to complete sub-goals and can interactively
or automatically apply them to the current proof.
Another innovative aspect of Matita, only marginally touched by this thesis,
is the embedded content-based search engine Whelp which is exploited to various
ends, from automatic theorem proving to avoiding duplicate work for the user.
We also discuss the (potential) reusability in other systems of the widgets presented
in this thesis and how we envisage the evolution of user interfaces for interactive
theorem provers in the Web 2.0 era.
18
Prince, Rawle C. S. "Aspects of the theory of containers within automated theorem proving." Thesis, University of Nottingham, 2011. http://eprints.nottingham.ac.uk/11793/.
Full textAbstract:
This thesis explores applications of the theory of containers within automated theorem proving. Container theory provides a foundational analysis of data types as containers, specified by a type $S$ of shapes and a function P assigning to each shape its set of positions for data.More importantly, a representation theorem guarantees that polymorphic functions between container data types are given by container morphisms, which are characterised by mappings between shapes and positions. Container theory is interesting, in this context, for the following reasons. A mechanism for representing and reasoning with ellipsis (the dots in x_1, x_2, ... , x_n) in lists, existing in the literature, has proved to be very useful for formalisations involving abstractions. Success with this mechanism came by means of a meta-level representation through which many functions that normally require recursive definitions can be given explicit ones. As a result, not only can induction and generalisation be eliminated from proofs but, by means of an associated portrayal system, the resulting proofs are also intuitive and much closer to informal mathematical proofs. This ellipsis mechanism, however, is not based on any formal theory, making it rather exiguous in comparison with rival techniques. There also remains questions about its scope and applications. Our aim is to improve this ellipsis mechanism. In this connection, we hypothesize that the theory of containers provides a formal underpinning for such representations. In order to test our hypothesis, we identify limitations of the ellipsis mechanism and show how they can be addressed within the theory of containers. We subsequently develop a new reasoning system based on containers, which does not suffer from these limitations. This judicious container-based system endorses representations of polymorphic rewrite rules using arithmetic, which naturally lends itself to applications of arithmetic decision procedures. We exploit this facet to develop a new technique for deciding properties of lists. Our technique is developed within a quasi-container setting: shape maps are given as piecewise-linear functions, while a new representation is derived for re-indexing functions that obviates the need for dependent types, which are fundamental in a judicious container approach. We show that this new setting enables us to represent and reason about a large class of properties.
19
Hunter, Christopher. "Agent-based proof support for interactive theorem proving /." [St. Lucia, Qld.], 2005. http://www.library.uq.edu.au/pdfserve.php?image=thesisabs/absthe19390.pdf.
Full text
20
Lapierre, Patrice. "Willow : extending Herby's semantic tree theorem-proving heuristics." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0022/MQ50812.pdf.
Full text
21
Matthews, S. "Metalevel and reflexive extension in mechanical theorem proving." Thesis, University of Edinburgh, 1994. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.657448.
Full textAbstract:
In spite of many years of research into mechanical assistance for mathematics it is still much more difficult to construct a proof on a machine than on paper. Of course this is partly because, unlike a proof on paper, a machine checked proof must be formal in the strictest sense of that word, but it is also because usually the ways of going about building proofs on a machine are limited compared to what a mathematician is used to. This thesis looks at some possible extensions to the range of tools available on a machine that might lend a user more flexibility in proving theorems, complementing whatever is already available. In particular, it examines what is possible in a framework theorem prover. Such a system, if it is configured to prove theorems in a particular logic T, must have a formal description of the proof theory of T written in the framework theory F of the system. So it should be possible to use whatever facilities are available in F not only to prove theorems of T, but also theorems about T that can then be used in their turn to aid the user in building theorems of T. The thesis is divided into three parts. The first describes the theory FS0, which has been suggested by Feferman as a candidate for a framework theory suitable for doing meta-theory. The second describes some experiments with FS0, proving meta-theorems. The third describes an experiment in extending the theory PRA, declared in FS0, with a reflection facility.
22
SCHROEDER, BRUNO. "A GRAPH BASED THEOREM PROVING PLATFORM WITH STRATEGIES." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2008. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=29093@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE EXCELENCIA ACADEMICA
Demonstrações em lógica podem tornar-se muito grandes e complexas. Para resolver problemas, e para estudar lógica, é comum valer-se de assistentes de demonstração. Um assistente de demonstração geral deve integrar ferramentas que ajudem a especificar as lógicas, as equações, os conjuntos de regras, e as estratégias de busca (semi) automática de demonstrações. A comunidade usuária de Provadores Automáticos de Teoremas conhece algumas ferramentas que atendem a estes requisitos. Entretanto, estas ferramentas não estão preparadas para lidar com demonstrações muito grandes. Trabalhos recentes sugerem que uma boa forma de chegar a demonstrações menores é usar grafos, ao invés de árvores, para representar demonstrações. Esta dissertação descreve e implementa uma máquina virtual baseada em grafo e um compilador para a confecção de provadores de teoremas baseados em grafo. Para validar a ferramenta, alguns estudos de casos e provadores de teoremas baseados em grafo são apresentados.
Proofs in logic can become very big and complex. For problem solving, and to teach logic, it is common the use of proof assistants. A general proof assistant should integrate tools to help users on specifying the logics, the formulas, the sets of rules, and the very strategy to perform (semi) automatic proof search. The Automatic Theorem Provers community is aware of some tools that were designed to fulfill these requirements. However, these tools do not take the (possibly) huge size of a proof. Recent works have pointed out that a good way to achieve shorter proofs is the use of graphs, instead of trees, to represent proofs. This dissertation describes and implements a graph-based virtual machine and a compiler for the production of graph-based theorem provers. Some case studies, standard as well as graph-based theorem prover, are illustrated in order to validate the tool.
23
Suen, Edward Shaw-Lee Carleton University Dissertation Computer Science. "Tableau-based theorem proving for representation and reasoning." Ottawa, 1987.
Find full text
24
Blanco, Martínez Roberto. "Applications of Foundational Proof Certificates in theorem proving." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLX111/document.
Full textAbstract:
La confiance formelle en une propriété abstraite provient de l'existence d'une preuve de sa correction, qu'il s'agisse d'un théorème mathématique ou d'une qualité du comportement d'un logiciel ou processeur. Il existe de nombreuses définitions différentes de ce qu'est une preuve, selon par exemple qu'elle est écrite soit par des humains soit par des machines, mais ces définitions sont toutes concernées par le problème d'établir qu'un document représente en fait une preuve correcte. Le cadre des Certificats de Preuve Fondamentaux (Foundational Proof Certificates, FPC) est une approche proposée récemment pour étudier ce problème, fondée sur des progrès de la théorie de la démonstration pour définir la sémantique des formats de preuve. Les preuves ainsi définies peuvent être vérifiées indépendamment par un noyau vérificateur de confiance codé dans un langage de programmation logique. Cette thèse étend des résultats initiaux sur la certification de preuves du premier ordre en explorant plusieurs dimensions logiques essentielles, organisées en combinaisons correspondant à leur usage en pratique: d'abord, la logique classique sans points fixes, dont les preuves sont générées par des démonstrateurs automatiques de théorème; ensuite, la logique intuitionniste avec points fixes et égalité,dont les preuves sont générées par des assistants de preuve. Les certificats de preuve ne se limitent pas comme précédemment à servir de représentation des preuves complètes pour les vérifier indépendamment. Leur rôle s'étend pour englober des transformations de preuve qui peuvent enrichir ou compacter leur représentation. Ces transformations peuvent rendre des certificats plus simples opérationnellement, ce qui motive la construction d'une suite de vérificateurs de preuve de plus en plus fiables et performants. Une autre nouvelle fonction des certificats de preuve est l'écriture d'aperçus de preuve de haut niveau, qui expriment des schémas de preuve tels qu'ils sont employés dans la pratique des mathématiciens, ou dans des techniques automatiques comme le property-based testing. Ces développements s'appliquent à la certification intégrale de résultats générés par deux familles majeures de démonstrateurs automatiques de théorème, utilisant techniques de résolution et satisfaisabilité, ainsi qu'à la création de langages programmables de description de preuve pour un assistant de preuveFormal trust in an abstract property, be it a mathematical result or a quality of the behavior of a computer program or a piece of hardware, is founded on the existence of a proof of its correctness. Many different kinds of proofs are written by mathematicians or generated by theorem provers, with the common problem of ascertaining whether those claimed proofs are themselves correct. The recently proposed Foundational Proof Certificate (FPC) framework harnesses advances in proof theory to define the semantics of proof formats, which can be verified by an independent and trusted proof checking kernel written in a logic programming language. This thesis extends initial results in certification of first-order proofs in several directions. It covers various essential logical axes grouped in meaningful combinations as they occur in practice: first,classical logic without fixed points and proofs generated by automated theorem provers; later, intuitionistic logic with fixed points and equality as logical connectives and proofs generated by proof assistants. The role of proof certificates is no longer limited to representing complete proofs to enable independent checking, but is extended to model proof transformations where details can be added to or subtracted from a certificate. These transformations yield operationally simpler certificates, around which increasingly trustworthy and performant proof checkers are constructed. Another new role of proof certificates is writing high-level proof outlines, which can be used to represent standard proof patterns as written by mathematicians, as well as automated techniques like property-based testing. We apply these developments to fully certify results produced by two families of standard automated theorem provers: resolution- and satisfiability-based. Another application is the design of programmable proof description languages for a proof assistant
25
Urbas, Matej. "Mechanising heterogeneous reasoning in theorem provers." Thesis, University of Cambridge, 2014. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.708290.
Full text
26
Gottliebsen, Hanne. "Automated theorem proving for mathematics : real analysis in PVS." Thesis, University of St Andrews, 2002. http://hdl.handle.net/10023/15046.
Full textAbstract:
Computer Algebra Systems (CASs), such as Maple and Mathematica, are now widely used in both industry and education. In many areas of mathematics they perform well. However, many well-established methods in mathematics, such as definite integration via the fundamental theorem of calculus, rely on analytic side conditions which CASs in general do not support. This thesis presents our work with automatic, formal mathematics using the theorem prover PVS. Based on an existing real analysis library for PVS, we have implemented transcendental functions such as exp, cos, sin, tan and their inverses, and we have provided strategies to prove that a function is continuous at a given point. In general, this is undecidable, but using certain restrictions we can still provide proofs for a large collection of functions. Similarly, we can prove that a function has a limit at a point. We illustrate how the extended library may be used with Maple to provide correct results where Maple's are incorrect. We present a case study of definite integration in the CASs axiom. Maple, Mathematica and Matlab. The case study clearly shows that apart from axiom the systems do not fully check the necessary conditions for the definite integral to exist, thus giving results varying from plain incorrect to correct, even if the latter is difficult to detect without manipulating the result. The extension and correction of the PVS library consists of around 1000 theorems proven by around 18000 PVS proof commands. We also have a test suite of 88 lemmas for the automatic checks for continuity and existence of limits. Thus we have devised and tested automatic computational logic support for the use of formal mathematics in applications, particularly computer algebra.
27
Hesketh, Jane Thurmann. "Using middle-out reasoning to guide inductive theorem proving." Thesis, University of Edinburgh, 1992. http://hdl.handle.net/1842/19842.
Full textAbstract:
Techniques derived from proof theory for logic alone have been insufficient as a basis for efficient, elegant automatic theorem proving. They concentrate on syntax, neglecting both strategy for particular domains and classes of problem, and guidance from modelling human mathematicians. A novel technique suggested by Bundy, developing ideas from Ernst & Newell, is to reason 'middle-out'. Often, the overall structure of a proof may be known, but its details must be fleshed out according to the individual theorem. Conventional research might use heuristic guidance to backtrack over all possibilities. Middle-out reasoning uses variables as place-holders for parameters still to be chosen. These place-holders become instantiated by the requirements of the subsequent proof. Decisions which would multiply the search space are postponed until more information is available. This is an exciting development in search control, making extensive use of strategic guidance and harnessing tools from human reasoning. This thesis reports research on its use for the synthesis of tail recursive functions from corresponding naive functions and for proofs requiring generalisation. It enables the development of a unified framework for generalisation. An existing proof planning and development system based on Martin-Lö Type Theory, Oyster/CLAM, is used as vehicle, augmented by higher order unification.
28
Mário, Oliveira Rodrigues Cleyton. "Component assembly and theorem proving in constraint handling rules." Universidade Federal de Pernambuco, 2009. https://repositorio.ufpe.br/handle/123456789/1821.
Full textAbstract:
Made available in DSpace on 2014-06-12T15:52:36Z (GMT). No. of bitstreams: 1
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2009Devido á grande demanda por softwares cada vez mais robustos, complexos e flexíveis, e, sobretudo, pelo curtíssimo tempo de entrega exigido, a engenharia de software tem procurado novos meios de desenvolvimento que supram satisfatoriamente essas demandas. Uma forma de galgar esses novos patamares de produtividade provém do uso de uma metodologia baseada em agentes que se comunicam e com isso, ao invés dos programas serem estritamente programados, o comportamento destes sistemas de software emerge da interação de agentes, robôs, ou subsistemas aut onomos, independentes, além de declarativamente especificados. Isto provê a habilidade para automaticamente configurá -los, otimizá-los, monitorá-los, adaptá-los, diagnosticá-los, repará-los e protegê-los dentro do ambiente. Contudo, um grande problema das linguagens declarativas é a falta de mecanismos que permitem a melhor estruturação de dados, facilitando portanto, o reuso. Portanto, esta dissertação explica o desenvolvimento de nova linguagem lógica declarativa para programar sistemas de raciocínio automático de uma forma modularizada: C2HR∨. A linguagem base escolhida para a extensão com componentes lógicos foi CHR. Os motivos para essa escolha são definidos ao longo da dissertação. Duas abordagens, portanto, são apresentadas: a primeira, conhecida como CHRat, foi desenvolvida numa parceria juntamente com o grupo de pesquisas CONTRAINTES do INRIA/Rocquencourt-Paris, onde o programador ´e o responsável direto por definir os componentes CHR, permitindo o seu reuso por outros componentes; a segunda aplicação, CHRtp, visa atender prioritariamente requisitos de completude e, por isso, se baseia em procedimentos lógicos de inferência como: o raciocínio para frente, o raciocínio para trás, e a resolução/factoring. A dissertação mostra também alguns exemplos práticos, onde uso de componentes facilita radicalmente sua implementação. As contribuições almejadas com essa dissertação são: a definição de uma família bem formalizada de provadores de teoremas automáticos, que podem trabalhar com sentenças especificadas em lógica horn ou em lógica de primeira ordem, a extensão de CHR como uma linguagem modular de propósito geral, a melhor estruturação de bases conhecimentos e até o uso em conjunto de bases heterogêneas, a definição de uma linguagem para a fácil e direta estruturação de dados por meio de componentes, dentre outras
29
Araragi, Tadashi. "Applications of automated theorem proving methods to multi-agent systems." 京都大学 (Kyoto University), 2006. http://hdl.handle.net/2433/143884.
Full text
30
Winterstein, Daniel. "Using diagrammatic reasoning for theorem proving in a continuous domain." Thesis, University of Edinburgh, 2005. http://hdl.handle.net/1842/642.
Full textAbstract:
This project looks at using diagrammatic reasoning to prove mathematical theorems. The work is motivated by a need for theorem provers whose reasoning is readily intelligible to human beings. It should also have practical applications in mathematics teaching. We focus on the continuous domain of analysis - a geometric subject, but one which is taught using a dry algebraic formalism which many students find hard. The geometric nature of the domain makes it suitable for a diagram-based approach. However it is a difficult domain, and there are several problems, including handling alternating quantifiers, sequences and generalisation. We developed representations and reasoning methods to solve these. Our diagram logic isn't complete, but does cover a reasonable range of theorems. It utilises computers to extend diagrammatic reasoning in new directions – including using animation. This work is tested for soundness, and evaluated empirically for ease of use. We demonstrate that computerised diagrammatic theorem proving is not only possible in the domain of real analysis, but that students perform better using it than with an equivalent algebraic computer system.
31
Heaton, John Edward. "Goal driven theorem proving using conceptual graphs and Peirce logic." Thesis, Loughborough University, 1994. https://dspace.lboro.ac.uk/2134/7706.
Full textAbstract:
The thesis describes a rational reconstruction of Sowa's theory of Conceptual Graphs. The reconstruction produces a theory with a firmer logical foundation than was previously the case and which is suitable for computation whilst retaining the expressiveness of the original theory. Also, several areas of incompleteness are addressed. These mainly concern the scope of operations on conceptual graphs of different types but include extensions for logics of higher orders than first order. An important innovation is the placing of negation onto a sound representational basis. A comparison of theorem proving techniques is made from which the principles of theorem proving in Peirce logic are identified. As a result, a set of derived inference rules, suitable for a goal driven approach to theorem proving, is developed from Peirce's beta rules. These derived rules, the first of their kind for Peirce logic and conceptual graphs, allow the development of a novel theorem proving approach which has some similarities to a combined semantic tableau and resolution methodology. With this methodology it is shown that a logically complete yet tractable system is possible. An important result is the identification of domain independent heuristics which follow directly from the methodology. In addition to the theorem prover, an efficient system for the detection of selectional constraint violations is developed. The proof techniques are used to build a working knowledge base system in Prolog which can accept arbitrary statements represented by conceptual graphs and test their semantic and logical consistency against a dynamic knowledge base. The same proof techniques are used to find solutions to arbitrary queries. Since the system is logically complete it can maintain the integrity of its knowledge base and answer queries in a fully automated manner. Thus the system is completely declarative and does not require any programming whatever by a user with the result that all interaction with a user is conversational. Finally, the system is compared with other theorem proving systems which are based upon Conceptual Graphs and conclusions about the effectiveness of the methodology are drawn.
32
Petschulat, Cap. "Transparency in formal proof." [Boise, Idaho] : Boise State University, 2009. http://scholarworks.boisestate.edu/td/54/.
Full text
33
Ghazizadeh, Behrad. "Hyperresolution for resolution logics." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp03/MQ39193.pdf.
Full text
34
Shanahan, Murray Patrick. "Exploiting dependencies in search and inference mechanisms." Thesis, University of Cambridge, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.252643.
Full text
35
Okoli, Ifeyinwa. "A novel term rewriting strategy for certain hierarchical AC-algebraic systems." Thesis, Loughborough University, 1989. https://dspace.lboro.ac.uk/2134/10641.
Full text
36
Boulton, Richard John. "Efficiency in a fully-expansive theorem prover." Thesis, University of Cambridge, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.319465.
Full text
37
Almulla, Mohammed Ali. "Analysis of the use of semantic trees in automated theorem proving." Thesis, McGill University, 1994. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=28662.
Full textAbstract:
Semantic trees have served as a theoretical tool for confirming the unsatisfiability of clauses in first-order predicate logic, but it has seemed impractical to use them in practice. In this thesis we experimentally investigated the practicality of generating semantic trees for proofs of unsatisfiability. We considered two ways of generating semantic trees. First, we looked at semantic trees generated using the canonical enumeration of atoms from the Herbrand base of the given clauses. Then, we considered semantic trees generated by selectively choosing the atoms from the Herbrand base using an improved semantic tree generator, AISTG. A comparison was made between the two approaches using the theorems from the "Stickel Test Set". In underlying the practicality of using semantic tree generators as mechanical theorem provers, another comparison was made between the AISTG and a resolution-refutation theorem prover "The Great Theorem Prover".
38
Lim, Hongping. "Translating timed I/O automata specifications for theorem proving in PVs." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/36803.
Full textAbstract:
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.Includes bibliographical references (leaves 68-70).
The timed input/output automaton modeling framework is a mathematical framework for specification and analysis of systems that involve discrete and continuous evolution. In order to employ an interactive theorem prover in deducing properties of a timed input/output automaton, its state-transition based description has to be translated to the language of the theorem prover. This thesis describes a tool for translating from TIOA, the formal language for describing timed input/output automata, to the language of the Prototype Verification System (PVS)--a specification system with an integrated interactive theorem prover. We describe the translation scheme, discuss the design decisions, and briefly present case studies to illustrate the application of the translator in the verification process.
by Hongping Lim.
M.Eng.
39
Roberts, Brian Glenn. "Modular Detection of Feature Interactions Through Theorem Proving: A Case Study." Link to electronic thesis, 2003. http://www.wpi.edu/Pubs/ETD/Available/etd-0821103-122029.
Full textAbstract:
Thesis (M.S.)--Worcester Polytechnic Institute.Keywords: theorem proving; modular verification; software verification; feature-oriented programming; feature interaction. Includes bibliographical references (p. 131-136).
40
Johnson, Robert David. "Parallel analytic tableaux systems." Thesis, Queen Mary, University of London, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.362777.
Full text
41
Duncan, Hazel. "The use of data-mining for the automatic formation of tactics." Thesis, University of Edinburgh, 2007. http://hdl.handle.net/1842/1768.
Full textAbstract:
As functions which further the state of a proof in automated theorem proving, tactics are an important development in automated deduction. This thesis describes a method to tackle the problem of tactic formation. Tactics must currently be developed by hand, which can be a complicated and time-consuming process. A method is presented for the automatic production of useful tactics. The method presented works on the principle that commonly occurring patterns within proof corpora may have some significance and could therefore be exploited to provide novel tactics. These tactics are discovered using a three step process. Firstly a suitable corpus is chosen and processed. One example of a suitable corpus is that of the Isabelle theorem prover. A number of possible abstractions are presented for this corpus. Secondly, machine learning techniques are used to data-mine each corpus and find sequences of commonly occurring proof steps. The specifics of a proof step are defined by the specified abstraction. The formation of these tactics is completed using evolutionary techniques to combine these patterns into compound tactics. These new tactics are applied using a naive prover as well as undergoing manual evalutation. The tactics show favourable results across a selection of tests, justifying the claim that this project provides a novel method of automatically producing tactics which are both viable and useful.
42
Lerner, Sorin. "Automatically proving the correctness of program analyses and transformations /." Thesis, Connect to this title online; UW restricted, 2006. http://hdl.handle.net/1773/7001.
Full text
43
Montano-Rivas, Omar. "Scheme-based theorem discovery and concept invention." Thesis, University of Edinburgh, 2012. http://hdl.handle.net/1842/6269.
Full textAbstract:
In this thesis we describe an approach to automatically invent/explore new mathematical theories, with the goal of producing results comparable to those produced by humans, as represented, for example, in the libraries of the Isabelle proof assistant. Our approach is based on ‘schemes’, which are formulae in higher-order logic. We show that it is possible to automate the instantiation process of schemes to generate conjectures and definitions. We also show how the new definitions and the lemmata discovered during the exploration of a theory can be used, not only to help with the proof obligations during the exploration, but also to reduce redundancies inherent in most theory-formation systems. We exploit associative-commutative (AC) operators using ordered rewriting to avoid AC variations of the same instantiation. We implemented our ideas in an automated tool, called IsaScheme, which employs Knuth-Bendix completion and recent automatic inductive proof tools. We have evaluated our system in a theory of natural numbers and a theory of lists.
44
Schmidt-Samoa, Tobias. "Flexible heuristic control for combining automation and user-interaction in inductive theorem proving." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=980519268.
Full text
45
Mackling, Thomas. "Contributions to automated theorem proving and formal methods with applications to control systems." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape11/PQDD_0018/NQ44506.pdf.
Full text
46
Meng, Jia. "The integration of higher order interactive proof with first order automatic theorem proving." Thesis, University of Cambridge, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.615216.
Full text
47
Frank, Mario. "TEMPLAR : efficient determination of relevant axioms in big formula sets for theorem proving." Master's thesis, Universität Potsdam, 2013. http://opus.kobv.de/ubp/volltexte/2014/7211/.
Full textAbstract:
This document presents a formula selection system for classical first order theorem proving based on the relevance of formulae for the proof of a conjecture. It is based on unifiability of predicates and is also able to use a linguistic approach for the selection. The scope of the technique is the reduction of the set of formulae and the increase of the amount of provable conjectures in a given time. Since the technique generates a subset of the formula set, it can be used as a preprocessor for automated theorem proving. The document contains the conception, implementation and evaluation of both selection concepts. While the one concept generates a search graph over the negation normal forms or Skolem normal forms of the given formulae, the linguistic concept analyses the formulae and determines frequencies of lexemes and uses a tf-idf weighting algorithm to determine the relevance of the formulae. Though the concept is built for first order logic, it is not limited to it. The concept can be used for higher order and modal logik, too, with minimal adoptions. The system was also evaluated at the world championship of automated theorem provers (CADE ATP Systems Competition, CASC-24) in combination with the leanCoP theorem prover and the evaluation of the results of the CASC and the benchmarks with the problems of the CASC of the year 2012 (CASC-J6) show that the concept of the system has positive impact to the performance of automated theorem provers. Also, the benchmarks with two different theorem provers which use different calculi have shown that the selection is independent from the calculus. Moreover, the concept of TEMPLAR has shown to be competitive to some extent with the concept of SinE and even helped one of the theorem provers to solve problems that were not (or slower) solved with SinE selection in the CASC. Finally, the evaluation implies that the combination of the unification based and linguistic selection yields more improved results though no optimisation was done for the problems.Dieses Dokument stellt ein System vor, das aus einer (großen) gegebenen Menge von Formeln der klassischen Prädikatenlogik eine Teilmenge auswählt, die für den Beweis einer logischen Formel relevant sind. Ziel des Systems ist, die Beweisbarkeit von Formeln in einer festen Zeitschranke zu ermöglichen oder die Beweissuche durch die eingeschränkte Formelmenge zu beschleunigen. Das Dokument beschreibt die Konzeption, Implementierung und Evaluation des Systems und geht dabei auf die zwei verschiedenen Ansätze zur Auswahl ein. Während das eine Konzept eine Graphensuche wahlweise auf den Negations-Normalformen oder Skolem-Normalformen der Formeln durchführt, indem Pfade von einer Formel zu einer anderen durch Unifikation von Prädikaten gebildet werden, analysiert das andere Konzept die Häufigkeiten von Lexemen und bildet einen Relevanzwert durch Anwendung des in der Computerlinguistik bekannten tf-idf-Maßes. Es werden die Ergebnisse der Weltmeisterschaft der automatischen Theorembeweiser (CADE ATP Systems Competition, CASC-24) vorgestellt und der Effekt des Systems für die Beweissuche analysiert. Weiterhin werden die Ergebnisse der Tests des Systems auf den Problemen der Weltmeisterschaft aus dem Jahre 2012 (CASC-J6) vorgestellt. Es wird darauf basierend evaluiert, inwieweit die Einschränkungen die Theorembeweiser bei dem Beweis komplexer Probleme unterstützen. Letztendlich wird gezeigt, dass das System einerseits positive Effekte für die Theorembeweiser hat und andererseits unabhängig von dem Kalkül ist, den die Theorembeweiser nutzen. Ferner ist der Ansatz unabhängig von der genutzten Logik und kann prinzipiell für alle Stufen der Prädikatenlogik und Aussagenlogik sowie Modallogik genutzt werden. Dieser Aspekt macht den Ansatz universell im automatischen Theorembeweisen nutzbar. Es zeigt sich, dass beide Ansätze zur Auswahl für verschiedene Formelmengen geeignet sind. Es wird auch gezeigt, dass die Kombination beider Ansätze eine signifikante Erhöhung der beweisbaren Formeln zur Folge hat und dass die Auswahl durch die Ansätze mit den Fähigkeiten eines anderen Auswahl-Systems mithalten kann.
48
DeCloss, Daniel P. "An analysis of Specware and its usefulness in the verification of high assurance systems." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2006. http://library.nps.navy.mil/uhtbin/hyperion/06Jun%5FDeCloss.pdf.
Full textAbstract:
Thesis (M.S. in Computer Science)--Naval Postgraduate School, June 2006.Thesis Advisor(s): Timothy Levin and Cynthia Irvine. "June 2006." Includes bibliographical references (p. 87-89). Also available in print.
49
Sabharwal, Ashish. "Algorithmic applications of propositional proof complexity /." Thesis, Connect to this title online; UW restricted, 2005. http://hdl.handle.net/1773/6938.
Full text
50
Goble, Tiffany Danielle. "Automate Reasoning: Computer Assisted Proofs in Set Theory Using Godel's Algorithm for Class Formation." Thesis, Georgia Institute of Technology, 2004. http://hdl.handle.net/1853/4767.
Full textAbstract:
Automated reasoning, and in particular automated theorem proving, has become a very important research field within the world of mathematics. Besides being used to verify proofs of theorems, it has also been used to discover proofs of theorems which were previously open problems. In this thesis, an automated reasoning assistant based on Godel's class theory is used to deduce several theorems.