Introduction to HOL


Book Description

Higher-Order Logic (HOL) is a proof development system intended for applications to both hardware and software. It is principally used in two ways: for directly proving theorems, and as theorem-proving support for application-specific verification systems. HOL is currently being applied to a wide variety of problems, including the specification and verification of critical systems. Introduction to HOL provides a coherent and self-contained description of HOL containing both a tutorial introduction and most of the material that is needed for day-to-day work with the system. After a quick overview that gives a "hands-on feel" for the way HOL is used, there follows a detailed description of the ML language. The logic that HOL supports and how this logic is embedded in ML, are then described in detail. This is followed by an explanation of the theorem-proving infrastructure provided by HOL. Finally two appendices contain a subset of the reference manual, and an overview of the HOL library, including an example of an actual library documentation.




Theorem Proving in Higher Order Logics


Book Description

This book constitutes the refereed proceedings of the 22nd International Conference on Theorem Proving in Higher Order Logics, TPHOLs 200, held in Munich, Germany, in August 2009. The 26 revised full papers presented together with 1 proof pearl, 4 tool presentations, and 3 invited papers were carefully reviewed and selected from 55 submissions. The papers cover all aspects of theorem proving in higher order logics as well as related topics in theorem proving and verification such as formal semantics of specification, modeling, and programming languages, specification and verification of hardware and software, formalization of mathematical theories, advances in theorem prover technology, as well as industrial application of theorem provers.




Isabelle/HOL


Book Description

This volume is a self-contained introduction to interactive proof in high- order logic (HOL), using the proof assistant Isabelle 2002. Compared with existing Isabelle documentation, it provides a direct route into higher-order logic, which most people prefer these days. It bypasses ?rst-order logic and minimizes discussion of meta-theory. It is written for potential users rather than for our colleagues in the research world. Another departure from previous documentation is that we describe Markus Wenzel’s proof script notation instead of ML tactic scripts. The l- ter make it easier to introduce new tactics on the ?y, but hardly anybody does that. Wenzel’s dedicated syntax is elegant, replacing for example eight simpli?cation tactics with a single method, namely simp, with associated - tions. The book has three parts. – The ?rst part, Elementary Techniques, shows how to model functional programs in higher-order logic. Early examples involve lists and the natural numbers. Most proofs are two steps long, consisting of induction on a chosen variable followed by the auto tactic. But even this elementary part covers such advanced topics as nested and mutual recursion. – The second part, Logic and Sets, presents a collection of lower-level tactics that you can use to apply rules selectively. It also describes I- belle/HOL’s treatment of sets, functions, and relations and explains how to de?ne sets inductively. One of the examples concerns the theory of model checking, and another is drawn from a classic textbook on formal languages.




Concrete Semantics


Book Description

Part I of this book is a practical introduction to working with the Isabelle proof assistant. It teaches you how to write functional programs and inductive definitions and how to prove properties about them in Isabelle’s structured proof language. Part II is an introduction to the semantics of imperative languages with an emphasis on applications like compilers and program analysers. The distinguishing feature is that all the mathematics has been formalised in Isabelle and much of it is executable. Part I focusses on the details of proofs in Isabelle; Part II can be read even without familiarity with Isabelle’s proof language, all proofs are described in detail but informally. The book teaches the reader the art of precise logical reasoning and the practical use of a proof assistant as a surgical tool for formal proofs about computer science artefacts. In this sense it represents a formal approach to computer science, not just semantics. The Isabelle formalisation, including the proofs and accompanying slides, are freely available online, and the book is suitable for graduate students, advanced undergraduate students, and researchers in theoretical computer science and logic.




VLSI Specification, Verification and Synthesis


Book Description

VLSI Specification, Verification and Synthesis Proceedings of a workshop held in Calgary from 12-16 January 1987. The collection of papers in this book represents some of the discussions and presentations at a workshop on hardware verification held in Calgary, January 12-16 1987. The thrust of the workshop was to give the floor to a few leading researchers involved in the use of formal approaches to VLSI design, and provide them ample time to develop not only their latest ideas but also the evolution of these ideas. In contrast to simulation, where the objective is to assist in detecting errors in system behavior in the case of some selected inputs, the intent of hardware verification is to formally prove that a chip design meets a specification of its intended behavior (for all acceptable inputs). There are several important applications where formal verification of designs may be argued to be cost-effective. Examples include hardware components used in "safety critical" applications such as flight control, industrial plants, and medical life-support systems (such as pacemakers). The problems are of such magnitude in certain defense applications that the UK Ministry of Defense feels it cannot rely on commercial chips and has embarked on a program of producing formally verified chips to its own specification. Hospital, civil aviation, and transport boards in the UK will also use these chips. A second application domain for verification is afforded by industry where specific chips may be used in high volume or be remotely placed.




Introduction to Singularities


Book Description

This book is an introduction to singularities for graduate students and researchers. It is said that algebraic geometry originated in the seventeenth century with the famous work Discours de la méthode pour bien conduire sa raison, et chercher la vérité dans les sciences by Descartes. In that book he introduced coordinates to the study of geometry. After its publication, research on algebraic varieties developed steadily. Many beautiful results emerged in mathematicians’ works. Most of them were about non-singular varieties. Singularities were considered “bad” objects that interfered with knowledge of the structure of an algebraic variety. In the past three decades, however, it has become clear that singularities are necessary for us to have a good description of the framework of varieties. For example, it is impossible to formulate minimal model theory for higher-dimensional cases without singularities. Another example is that the moduli spaces of varieties have natural compactification, the boundaries of which correspond to singular varieties. A remarkable fact is that the study of singularities is developing and people are beginning to see that singularities are interesting and can be handled by human beings. This book is a handy introduction to singularities for anyone interested in singularities. The focus is on an isolated singularity in an algebraic variety. After preparation of varieties, sheaves, and homological algebra, some known results about 2-dim ensional isolated singularities are introduced. Then a classification of higher-dimensional isolated singularities is shown according to plurigenera and the behavior of singularities under a deformation is studied.




House of Leaves


Book Description

“A novelistic mosaic that simultaneously reads like a thriller and like a strange, dreamlike excursion into the subconscious.” —The New York Times Years ago, when House of Leaves was first being passed around, it was nothing more than a badly bundled heap of paper, parts of which would occasionally surface on the Internet. No one could have anticipated the small but devoted following this terrifying story would soon command. Starting with an odd assortment of marginalized youth -- musicians, tattoo artists, programmers, strippers, environmentalists, and adrenaline junkies -- the book eventually made its way into the hands of older generations, who not only found themselves in those strangely arranged pages but also discovered a way back into the lives of their estranged children. Now this astonishing novel is made available in book form, complete with the original colored words, vertical footnotes, and second and third appendices. The story remains unchanged, focusing on a young family that moves into a small home on Ash Tree Lane where they discover something is terribly wrong: their house is bigger on the inside than it is on the outside. Of course, neither Pulitzer Prize-winning photojournalist Will Navidson nor his companion Karen Green was prepared to face the consequences of that impossibility, until the day their two little children wandered off and their voices eerily began to return another story -- of creature darkness, of an ever-growing abyss behind a closet door, and of that unholy growl which soon enough would tear through their walls and consume all their dreams.




Certified Programming with Dependent Types


Book Description

A handbook to the Coq software for writing and checking mathematical proofs, with a practical engineering focus. The technology of mechanized program verification can play a supporting role in many kinds of research projects in computer science, and related tools for formal proof-checking are seeing increasing adoption in mathematics and engineering. This book provides an introduction to the Coq software for writing and checking mathematical proofs. It takes a practical engineering focus throughout, emphasizing techniques that will help users to build, understand, and maintain large Coq developments and minimize the cost of code change over time. Two topics, rarely discussed elsewhere, are covered in detail: effective dependently typed programming (making productive use of a feature at the heart of the Coq system) and construction of domain-specific proof tactics. Almost every subject covered is also relevant to interactive computer theorem proving in general, not just program verification, demonstrated through examples of verified programs applied in many different sorts of formalizations. The book develops a unique automated proof style and applies it throughout; even experienced Coq users may benefit from reading about basic Coq concepts from this novel perspective. The book also offers a library of tactics, or programs that find proofs, designed for use with examples in the book. Readers will acquire the necessary skills to reimplement these tactics in other settings by the end of the book. All of the code appearing in the book is freely available online.




Isabelle


Book Description

This volume presents the proceedings of the First International Static Analysis Symposium (SAS '94), held in Namur, Belgium in September 1994. The proceedings comprise 25 full refereed papers selected from 70 submissions as well as four invited contributions by Charles Consel, Saumya K. Debray, Thomas W. Getzinger, and Nicolas Halbwachs. The papers address static analysis aspects for various programming paradigms and cover the following topics: generic algorithms for fixpoint computations; program optimization, transformation and verification; strictness-related analyses; type-based analyses and type inference; dependency analyses and abstract domain construction.




Theorem Proving in Higher Order Logics


Book Description

This book contains the refereed proceedings of the 20th International Conference on Theorem Proving in Higher Order Logics, TPHOLs 2007, held in Kaiserslautern, Germany, September 2007. Among the topics of this volume are formal semantics of specification, modeling, and programming languages, specification and verification of hardware and software, formalization of mathematical theories, advances in theorem prover technology, as well as industrial application of theorem provers.