bluuebunny/crossref_metadata_2025 huggingface dataset:
Proof with connectives
Authors: Bornat Richard
Published: November 2023

The target of this part of the book is neither syntax nor semantics nor the properties of Natural Deduction, it’s formal proof. Proofs which use only the connectives and the constant symbols are pretty straightforward.
Indicators
Authors: Kaye Richard
Published: November 2023

Suppose M is a nonstandard model of PA and we are interested in finding initial segments I⊆e  M having a certain property Q. An indicator for Q is a function Y: M  2⟶M such that, for each a ℕ iff there is an initial segment I between a and b and having the property Q. This notion was devised by Paris and Kirby in the 1970s to study the structure of models of PA, but it soon became clear that indicators were the key to several particularly interesting independence results. Paris and Harrington later used these ideas to exhibit the first examples of mathematically interesting statements that are true in ℕ but unprovable in PA, and we shall present an introduction to this material in Section 14.3 below.
Recursive saturation
Authors: Kaye Richard
Published: November 2023

There are many reasons for studying satisfaction classes: they are a useful vehicle for understanding the strengths and limitations of Tarski's definition of truth; the notion of a full inductive satisfaction class leads naturally to a new theory of arithmetic extending PA in which the consistency of PA and the Paris-Harrington statement can be proved; and there are a good number of naturally occurring examples arising from the arithmetized completeness theorem or from nonstandard models of set theory (see Exercise 15.4).
Reliability covering problems
Authors: Shier Douglas R
Published: November 2023

This chapter studies a type of reliability problem in which a given set S needs to be covered by certain of its subsets. The subsets are available for use on a random and independent basis with known probabilities. It is of interest to calculate the probability that the entire set S is ‘covered’ by the operating subsets: i.e., every element of Sis present in some available subset. As an example of such a problem, consider a mass transit system containing a number of bus routes and the stops they serve. Because of maintenance or staffing problems, a particular bus route might not always be in service: specifically the route is only known to operate (or be available) with some fixed probability. A useful performance measure for the transit system is therefore the probability that each stop is served by some operating bus route. There are a number of other possible applications of this model, such as evaluating the reliability of delivery routes (needed to cover customer demands) or determining the reliability of flight schedules for aircraft (serving airports). Another application is discussed more fully in Section 7.1, and a general description of the reliability covering problem is presented in Section 7.2. It is shown that solving the covering problem is, in fact, equivalent to calculating the reliability of a coherent system, which is known to be mathematically difficult. Consequently, the general covering problem is provably hard.
An Introduction To Sequential Ode Methods
Authors: Burrage Kevin
Published: November 2023

Since this monograph is concerned with an exposition of efficient methods for the numerical solution of systems of differential equations in a parallel computing environment, it is necessary to have a thorough insight into extant sequential methods. There is no space in this monograph to give a comprehensive discussion on all aspects of sequential algorithms for IVPs, rather, this monograph will attempt to give a flavour of this work and will emphasize techniques which have relevance to the development of parallel algorithms.
Direct Methods For Odes
Authors: Burrage Kevin
Published: November 2023

Much of the contents of the previous chapters have been necessary for an understanding of subsequent material on parallel differential equation techniques. This material on parallel techniques has essentially been divided into two sections. In Chapters 5 and 6 the various different forms that parallelism can take when solving differential equations are discussed with the main focus being the analysis and construction of direct and iterative methods for exploiting small-scale parallelism. The underlying concepts here are parallelism across the method and parallelism across the steps.
Local set theories
Authors: Chapman Jonathan , Rowbottom Frederick
Published: November 2023

This preliminary chapter introduces a language (and local set theory) for a topos (as described in Section 1.2). It can be skipped by a reader familiar with any such language. This presentation is essentially due to Zangwill (1977), and is similar to that of Boileau and Joyal (1981). It has been included partly to make the work more self-contained but mainly to facilitate Chapter 9, where the same material is covered relative to a topos.
Topologies and sheaves
Authors: Chapman Jonathan , Rowbottom Frederick
Published: November 2023

In this chapter, some basic theory of topoi is rehearsed in S, concerning topologies and sheaves. We follow Chapman (1982), § §3-5, which makes use of the logic of a topos. Bell (1986) and Veit (1981) do likewise (externally). See Johnstone (1977) for a purely categorical treatment. However, it is not necessary to refer to any of these, in order to understand what follows.
The Fibonacci sequence, generalized Fibonacci sequences, and related topics
Authors: Cofman Judita
Published: November 2023

One of the most engaging puzzles in the history of mathematics was formulated by Leonardo of Pisa, nicknamed Fibonacci (1170-1250) in his celebrated book Liber abaci: How many pairs of rabbits will be produced in a year, beginning with a single pair, if in every month each pair bears a new pair which becomes productive from the second month on?
Reflected light rays and real numbers; a theorem of Kronecker
Authors: Cofman Judita
Published: November 2023

A light ray is reflected from a straight line mirror in such a way that the angle between the incoming ray and the mirror is equal to the angle between the reflected ray and the mirror; moreover, the incoming ray, the mirror, and the reflected ray belong to a common plane (Fig. 1.24).
The Chinese remainder theorem and invisible lattice points
Authors: Cofman Judita
Published: November 2023

The fourth-century Chinese mathematical text, titled Sun Tsu San Ching (Master Sun’s arithmetic manual), contains the following problem: There is an unknown number of objects. When counted in ‘threes’, the remainder is 2; when counted in ‘fives’, the remainder is 3; and when counted in ‘sevens’, the remainder is 2. How many objects are there? Sun Tsu describes a way for solving the problem and provides an answer to the question.
Chapter III
Authors: Cofman Judita
Published: November 2023

Let a/b be a reduced fraction such that 0 < a/b < 1. First we shall prove the following.

a/ b has a finite number of digits in its decimal expansion if and only if its denominator b is of the form 2∝ . 5βfor some non-negative integers∝.
The Mfe Method Of Miller
Authors: Baines M J
Published: November 2023

The Moving Finite Element (MFE) method was introduced by Keith Miller (Miller and Miller 1981, Miller 1981) in order to obtain. numerical solutions of problems with steep moving fronts. The main ideas of the method are discussed in this chapter. The approach adopted is essentially that of Miller’s original papers since this appears to be the best way of introducing the subject. In later chapters however we shall describe other equivalent viewpoints which show the method in a different light.
Mfe In Higher Dimensions
Authors: Baines M J
Published: November 2023

One of the main attractions of the MFE method has been its ability to deal with problems in two and three dimensions on unstructured triangular and tetrahedral grids. In Section 1.4 of Chapter 1 we wrote down the weak forms (1.36) and (1.37) of the MFE residual minimization in any number of dimensions, leading to the matrix equation (1.40), namely,
Results From The Mfe Method
Authors: Baines M J
Published: November 2023

Although a full understanding of the workings of the MFE method is yet to come, this has not prevented the application of the method using penalty functions to a wide variety of problems by, among others, Gelinas et al. (1981), Mosher (1985), Hrymak et al. (1986), Dukowicz (1984), Juarez-Romero et al. (1988), Demkowicz (1984). The most prolific exponents of the method have been Miller and Carlson, using the global GWMFE formulation together with penalty functions and a stiff implicit solver for the time-stepping. Many other workers have followed a similar path, and between them these authors have covered a wide spectrum of practical problems, in some cases obtaining simulations not available by other numerical methods.
The Role Of The Mfe Method
Authors: Baines M J
Published: November 2023

In this chapter we review the MFE method and the properties proved for it so far in this book (together with some new ones) and assess the rôle of the method in the approximate solution of PDEs.
Best Fits With Adjustable Nodes
Authors: Baines M J
Published: November 2023

In this chapter we discuss the problem of finding optimal L fits to continuous functions with adjustable nodes via piecewise linear discontinuous functions. This gives the search an extra dimension, simplifying the conditions to be satisfied and linking strongly with the MFE procedure. Using a direct variational approach but with non-standard variations, interpreted numerically, new algorithms are devised, based on a two stage iteration process similar to that in Chapter 4, whose limit is the required best approximation. In this way we reduce the nonlinearity of the problem (virtually eliminating it for linear fits in one dimension) and obtain algorithms which are fast and robust. Using a similar approach, we also derive algorithms providing best piecewise constant L fits with adjustable nodes.
Discussion And Conclusion
Authors: Baines M J
Published: November 2023

In this final chapter we discuss some of the implications of the investigation into MFE and related methods given in this book, and consider some of the wider implications.
Transcendental Numbers
Authors: Rose H E
Published: November 2023

A real or complex number which satisfies no polynomial equation with algebraic coefficients is called transcendental (see Section 1 of Chapter 5). Liouville, in 1844, was the first to show that transcendental numbers exist. although we now know that almost all real or complex numbers have this property.
Genera And The Class Group
Authors: Rose H E
Published: November 2023

We begin by introducing the equivalence of forms modulo a prime (that is. studying forms locally; see Section 3 of Chapter 3), this gives a new class structure with classes called genera. Secondly, we will show that the set of equivalence classes (in the original sense) forms a group, called the class group, under the operation of composition of forms defined below. The genera are cosets of this group and this fact enables us to derive some arithmetical properties of the class group. Finally, we give a formula for h(d), the order of the class group for discriminant d.
The Prime Numbers
Authors: Rose H E
Published: November 2023

The study of the primes is one of the most important branches of number theory. The only other branch of similar importance is Diophantine equations and this will be considered in the final three chapters. The literature on the prime numbers is very extensive beginning with Pythagoras and Euclid; even so, many problems remain. There are two pre-eminent results: Dirichlet’s theorem and the prime number theorem (PNT).
Elliptic Curves: Further Results And Applications
Authors: Rose H E
Published: November 2023

In Chapter 3 we discussed the Hasse principle and noted that it does not apply to curves of genus L which includes the elliptic curves. Nevertheless, many properties of a curve C defined over a global field (Q for example) can be deduced from properties of C defined over a local field or a finite field. Most of this work is beyond the scope of this book, but we shall begin the study of curves defined over finite fields, define the corresponding group of ‘rational’ points, and give three applications.
Elasticity and anelasticity: continuous viewpoint*
Authors: Maugin Gerard A
Published: November 2023

The elastic behaviour of a material is characterized anthropomorphically by stating that it ‘remembers’ only one of its previous states, namely the natural, unstressed and unstrained state. Whether such a state had actually been occupied in the past or not, or whether it is a mere abstract notion which helps one to give an unambiguous mathematical definition, is another matter. In any case, whenever the ‘causes’ of motion and deformation are removed, the material must recover its original state and, therefore, such behaviour certainly does not exhibit thermodynamical irreversibility. Accordingly, all properties are derived from a potential, the elastic energy potential, usually taken as a function of strains.
Coupled fields in elasticity
Authors: Maugin Gerard A
Published: November 2023

In systems with electromagnetomechanical coupling, the electromagnetic component invariably gives rise to nonlinear effects or enhances them. The coupling with the electromagnetic component is also used to measure these effects. Some of the example of these systems are: (i) the elastic piezoelectric semiconductors, (ii) the already mentioned elasticferroelectrics of the molecular-group type and (iii) the elastic ferromagnets where nonlinearities could result from their semiconducting property, or large angular deviations, or even the up and down flipping of the molecular groups or the magnetic spins, respectively. Dispersion usually arises from the collective behaviour of sets of individual objects (such as magnetic spins) which are coupled through relatively long-range interactions. The ordering characteristics underlying several of these phases is essential in that respect.
Shock waves and phase-transition fronts in thermoelastic crystals
Authors: Maugin Gerard A
Published: November 2023

When structure is ignored, shock waves and phase-transition fronts both belong to the class of discontinuity fronts across which the first-order space-time derivatives of the basic fields undergo finite discontinuity jumps. This classification of discontinuity fronts goes back to celebrated studies by the mathematician Jacques Hadamard (1865-1963), who built on notions introduced by J. C. Maxwell (1831-1879), G. Riemann (1826--1866) and P. Duhem (1861-1916).
Reversible and non-dissipative processes
Authors: Ericksen J L
Published: November 2023

Of concern here are the various theories which are consistent with traditional and some newer views of thermodynamics, involving some specified set of admissible thermodynamic processes, with some prescription for calculating entropy changes and dissipation for these. Particularly, my aim is to encourage others to strive to clear up various questions related to the general theory of thermodynamic equilibrium, it being my experience that the literature on this is quite confused and confusing. There are various theories of equilibrium which involve considering some thermodynamic potential but with no explicit consideration of dissipation. For part of the discussion, we need to include these. Another kind of exception, closer to Albert Green‘s interests, will be mentioned in section 4. To focus our thoughts, it seems helpful to consider the following questions.
Convexity considerations for the biharmonic equation in plane polars with applications to elasticity
Authors: Flavin J N
Published: November 2023

Solutions of the biharmonic equation are considered in the arch-like region 0 < θ < α < r < b in the presence of boundary conditions ϕ = ϕ = 0 on the edges r = a, r = b ((r, θ) denoting plane polar coordinates). A cross-sectional measure F(θ) of the solution is considered and is proved to be convex in 0 for b/a ≤ exp π. If, additionally, the condition ϕ = ϕθ = 0 obtains on the edge 0 = α, F(θ) satisfies an enhanced inequality (generalized convexity); upper bounds for F(θ) in terms of suitable data follow.
Finite deformations of a fibre-reinforced cantilever: distributed-load solutions
Authors: England A H , Rogers T G , Bradford I D R
Published: November 2023

This paper considers the finite plane deformations of a cantilever beam composed of an elastic ideal fibre-reinforced material. The fibres are aligned along the beam. The cantilever is deformed by loads distributed over its lateral (upper and lower) surfaces. It is assumed that these forces either are ‘dead loads’ which do not change in magnitude or direction throughout the deformation, or that they act normally to the deformed lateral surfaces of the beam. In both cases solutions are derived using stationary-energy methods.
Explicit Q-functions
Authors: Hoffman P N , Humphreys J F
Published: November 2023

More details concerning the Q-functions are given in this chapter. Motivated by Theorem 7.21, we first define a function Q  a for each integer sequence α; but then immediately show that if α: is not a strict partition, then Q  a is either zero or is a multiple of Q  A for a certain γ in 𝒟. The Q  a are needed in Chapter 10, but they also play a role in a Laurent identity, (9.5) here. This is a generating “expression” for the Q  a. It could be re-interpreted as a raising operator formula, such as occurs in the theory of Schur functions, but we prefer to use the Laurent formulation. It leads to four more formulae for Q  A.
Construction of the Irreducible Negative Representations
Authors: Hoffman P N , Humphreys J F
Published: November 2023

In this chapter, we give a construction due to Nazarov (1989) of the irreducible negative representations of ˜. They are obtained from those of the group Ŝn (as defined in Remark (3) after Theorem 2.11) by multiplying the matrix for each generator sk by i to give the matrix for tk. We shall follow Nazarov closely, giving the matrices for Ŝn.
Combinatorial and Skew Q-functions
Authors: Hoffman P N , Humphreys J F
Published: November 2023

The first objective of this chapter is to find combinatorial descriptions of two sets of numbers: those which occur (i) as inner products , and (ii) as coefficients in the expression of the product Q  v  Q  μ in terms of the basis |Q  λ|. The fom1er is essentially a special case of the latter, and leads to an enumerative description of the coefficients in the polynomial Qλ(X); in particular, these coefficients are non-negative integers. It also leads to a strengthening of the unitriangularity phenomena, in both the definition of Q  λ, and in Theorem 8.6 relating the irreducibles <λ> to the induced representations ξλ. Schur’s fundamental orthogonality identity then yields an important enumerative result connecting the marked shifted tableau occurring in the above formulae with integer matrices which have “marked” entries.
The Shjffed Knuth Algorithm
Authors: Hoffman P N , Humphreys J F
Published: November 2023

This chapter will be devoted entirely to giving a second, purely combinatorial. proof of Theorem 12.11. We describe a number of algorithms and their inverses, and combine them to provide an explicit bijection. This material is the backbone of the combinatorial approach lo Q-functions. We shall make one further foray into this side of the subject, in the second half of the next chapter. The reader should consult the papers referred to in the notes to this and the next chapter for further details, as well as for alternative methods.
Prologue
Authors: Gene Golub
Published: November 2023

I am very honoured to be able to make the opening remarks at this meeting dedicated to Jim Wilkinson. This promises to be a very interesting and stimulating meeting-one that Jim would have greatly enjoyed. Although we are all saddened by his death, we should remember him at this meeting with the pleasure and happiness he gave to all of us.
Evolution of numerical software for dense linear algebra
Authors: Dongarra Jack , Hammarling Sven
Published: November 2023

We trace the development of numerical software for dense linear algebra from the early days of computers through to work in progress for modern high-performance machines.
Introduction
Authors: Croarken Mary
Published: November 2023

In considering the centralization of scientific computation this book attempts to link together two areas of study: the prehistory of computers and the attitudes of scientists towards using machine methods of computation. More specifically, it examines how scientific computation was organized in Britain from the early 1900s to the mid-fifties. That is, from the time desk calculators began to become both readily available and reliable, to the invention and construction of the stored program computer. During this 50-year period the way in which computation was carried out changed significantly not only in terms of the technology used but also in the way in which computation was organized and financed. Advances in applied science meant that scientists and administrators had to find new ways of coping with an increasing demand for computation. The idea of centralizing computer power and providing user support developed slowly during the period. The concept of centralized compution culminated in 1945 with the creation of the National Physical Laboratory (NPL) Mathematics Division.
Background: aids to computation
Authors: Croarken Mary
Published: November 2023

The most commonly used computational aids available in the 1900s were mathematical tables, slide rules, nomograms, mathematical instruments, and desk calculating machines. Of these only the mathematical tables and the desk calculators lent themselves to the type of large-scale repetitive calculations which could be centralized with advantage. The increasing use of desk calculating machines during the early twentieth century laid the foundation for computing centres to become a possibility but nevertheless mathematical tables, slide rules, and mathematical instruments had an important role to play.
The National Physical Laboratory Mathematics Division: a national computing centre
Authors: Croarken Mary
Published: November 2023

During 1946 the NPL Mathematics Division became fully operational. By the end of that year the Division had a staff of 50 divided into five sections: the General Computing Section, the Punched Card Section, the Differential Analyser Section, the Statistics Section, and the Automatic Computing Engine (ACE) Section. The Mathematics Division was operating more or less within the guidelines set out in the 1944 DSIR Interdepartmental Committee Report. From the description of a Central Mathematics Station as outlined in that report it might be assumed that the NPL Mathematics Division also embodied the concept of a computing centre defined by the characteristics given in Chapter l. However, before such a conclusion can be reached it is important to examine the NPL Mathematics Division more closely.
Theory and practice of tern poral logic programming
Authors: Orgun Mehmet A , Wadge* William W
Published: November 2023

Chronolog is a logic programming language based on temporal logic and possible worlds semantics. Temporal logic allows us to describe dynamic and time-dependent properties of certain problems in a direct and problem-oriented way. In Chronolog programs, users specify time-varying predicates; thus the notion of dynamic change and dataflow-style of non-terminating computations can be naturally specified in Chronolog. The declarative semantics of Chronolog programs can be characterized in terms of the least model semantics; hence Chronolog does not have some of the problems associated with non-logical extensions of logic programming. Chronolog extended with choice predicates (arbitrary single-valued relations) is suitable for modelling mutual exclusion problems such as that of the dining philosophers. A natural extension of Chronolog with modules allows us to specify objects with internal memory.
A promenade from provability to consistency
Authors: * Philippe Balbiani
Published: November 2023

The semantics of logic programming with negation is addressed by means of modal logic. Inspired by the well-known three-valued semantics, a modal completion formula of logic programs is defined with the help of modal operators. Depending on the logical be haviour of these operators, the modal formula completion will alternatively possess the soundness and completeness properties with respect to ‘SLDNF-refutability’ or the soundness and completeness properties with respect to ‘non-SLDNF-refutability’. It will allow a logical characterization of some properties possessed by SLDNF proof trees as well. Lastly, since one of these properties is closely related to the closed-world assumption rule, the completion formula will give an almost complete proof procedure for this non-monotonic rule of inference.
Selected papers
Authors: Hogger Christopher John
Published: November 2023

The following papers are worth reading for their lucid exposition, foundational importance a,,d historical significance.

"A machine-oriented logic based on the resolution principle" by J. A. Robinson. Journal of the ACM 12, 1965, pp.23--41.

"Computation and deduction" by P. J. Hayes.

Proc. of the 2nd Symposium on the Mathematical Foundations of Computer Science, Czechoslovak Academy of Sciences, 1973, pp. l 05-118.

"Predicate logic as a programming language" by R. A. Kowalski.

Proc. of IFIP-74, North Holland Publishing Company, Amsterdam, 1974, pp. 569-574.
The alleged deficiencies
Authors: Hogger Christopher John
Published: November 2023

Fifteen years ago logic programming was barely visible in the computing landscape. But during the ten years that followed its acclaim spread far and wide, and many of those working in the field felt there was quite a good chance that it would substantially displace older and supposedly less satisfactory formalisms. The Japanese had invested heavily in it for the purposes of their Fifth Generation Computer Systems Project, and the number of world-wide sites in which Prolog was used numbered tens-perhaps even hundreds--of thousands. There was a lot of interest in expert systems, many of which were written in Prolog. Industries in the UK and elsewhere in Europe readily joined with academia in various programmes of funded research and development, and numerous companies came into being as suppliers of logic programming technology.
More model theory definitions
Authors: Hogger Christopher John
Published: November 2023

An interpretation which gives the value true to a sentence is said to satisfy

the sentence; such an interpretation is called a model for the sentence.

Example-the interpretation first chosen in Theme 11 is a model for the sentence likes(chris, mummy).

An interpretation.which does not satisfy a sentence is called a counter¬ model for that sentence.

By extension, we also have the notion of a model (or counter-model) for a set of sentences: an interpretation is a model for the set if and only if it is a model for each of the set’s members.

A sentence which has at least one model is said to be satisfiable.

A sentence which has no models is said to be unsatisfiable.

Example- likes(chris, mummy) is satisfiable.
Moving literals within clauses
Authors: Hogger Christopher John
Published: November 2023

The classical representation of a clause is a disjunction of literals. However, any such clause can be rewritten, with no loss of equivalence, as a sentence in conditional format having the form disjunction of literals if conjunction of literals Thus a clause such as A or B or ,C or ,D or ,E can be rewritten, for example, in this conditional format or B if C&D&E

Starting with the classical format, we obtained this new format by disjoining, on the left of an ‘if’, all the positive literals and by conjoining, on the right of the ‘if’, all the atomic parts of the negative literals. That the two versions are equivalent is owed solely to the logical interpretations of the connectives:
Some useful conversions
Authors: Hogger Christopher John
Published: November 2023

In the logic programming context some species of conversion are particularly common. To perform these conversions it is easier to follow pre-defined schemata than to work through all the stages of the algorithm previously described.
Implication and validity
Authors: Hogger Christopher John
Published: November 2023

We remarked earlier that logic programming does not normally make explicit use of valid sentences. Indeed, for the most part such sentences are a nuisance when they occur (typically inadvertently) within logic programs, for they tend to plunge execution into infinite loops.
Computations and answers
Authors: Hogger Christopher John
Published: November 2023

Various species of derivation may evolve from a query at the root of a search tree. Let us take another look at the tree obtained using the ‘append’ program for the query

In any such tree, a derivation beginning with the root query (Ql) is called a computation from that query. In general, a tree may contain both finite computations and infinite computations (‘loops’).
The unification algorithm
Authors: Hogger Christopher John
Published: November 2023

There are many different species of algorithms available for computing most¬ general unifiers. The one most commonly employed in logic program interpreters is known as Robinson’s Algorithm (named after the discoverer of resolution).Its task is as follows. Given as input two atoms of the form

in which the ri and ti are any terms, its aim is to decide whether the atoms are unifiable and-if they are-to deliver as output their most-general unifier; if they are not unifiable then the output is the message “failure”.

In the initial set-up, all the term-pairs < ri, ti > are stored on a stack S. Another stack 0, initially empty, is made available for accommodating those bindings (called ‘replacements’ in earlier Themes) which the algorithm will construct in the course of comparing each pair of terms on S. These two stacks are the only data structures required.
Varying the selection rules
Authors: Hogger Christopher John
Published: November 2023

Given a query and a program, the choice of computation rule determines a corresponding SLD-tree. Assuming that the search procedure is top-down and depth-first, the choice of search rule determines only the order in which the tree’s computations are generated. Below we sketch some SLD-trees generated from a simple path-finding problem (seeking paths commencing at node ‘a’).
Incremental construction of the minimal model
Authors: Hogger Christopher John
Published: November 2023

There is a simple incremental method for constructing the minimal model of any definite program P. This method is not strictly an algorithm since, in the case where MM(P) is infinite, it may not complete the construction in a finite number of steps; however, the more steps we perform, the better the approximation.

The method starts by choosing some interpretation I 1<;;;B(P). Later on we shall see that there is a preferred choice of I1 and that not all choices are adequate. Choosing I1 can be viewed as guessing which atoms have to be true in any model of P. Now consider any clause in G(P)
Unfolding programs
Authors: Hogger Christopher John
Published: November 2023

We now introduce a very useful form of partial evaluation called unfolding, which is one of the key techniques employed for performing program transformation. This technique operates wholly upon the program clauses without regard to any particular query, and its effect is indicated by Figure 49.L
Folding programs
Authors: Hogger Christopher John
Published: November 2023

Folding is a program transformation technique which is essentially the inverse of unfolding. The effect of any single folding step is to derive one new clause from some existing clause; the new clause can then replace the old one to yield a new program. Figure 53.1 gives an indication of what is involved.
Extending SLD with finite failure
Authors: Hogger Christopher John
Published: November 2023

Although the SLD paradigm is theoretically adequate for all computational purposes, the pure Horn-clause language on which it is based is unlikely to become the dominant logic-programming language of the future. In fact it never has been the mainstream logic-programming language, as every Prolog programmer will testify-writing a logic program for a real-world application nearly always seems to require the expression of some intention or other for which there is apparently no practical representation in pure Horn-clause logic. It is futile to resist this fact of computational life; in the end, the cumulative and collective experience of serious practitioners has to be respected.

The designers of Prolog anticipated this and consequently felt obliged to add many non-logical extensions to the Horn-clause kernel. In doing so they placed greater weight upon the concrete needs of the practitioners than upon the more abstract desires of the theoreticians. A lot of research effort has since been devoted to the problem of rendering those extensions either semantically intelligible or methodologically redundant. A substantial part of that effort has concentrated upon one particular issue-the finite failure extension.
Special applications of SLDNF
Authors: Hogger Christopher John
Published: November 2023

The SLDNF inference system has come to be accepted as a staple feature of the logic programming paradigm. It is perhaps in recognition of this that programs and queries containing fail calls are now commonly referred to as normal programs and normal queries-they are what you would normally expect to use in practical applications. Up to a point, Prolog employs SLDNF in order to implement its ‘not’ primitive, which is merely fail by another name. Most versions of Prolog do not, however, enforce the safety requirement, leaving this responsibility instead to the programmer.

Given the semantic complications attending SLDNF, could we make do without it and simply stick to SLD? In theory we could do so, since the SLD paradigm is, in principle, capable of computing everything that is computable. But in practice we would pay a heavy price-our programs would be less concise and their executions less efficient. Consider, for example, the problem of showing positively that the element 3 is not a member of the set { 1, 2}. Without the use of fail we are obliged to write a program computing a relation ‘not_mem’ relying, ultimately, upon some built-in inequality primitive -/-. Moreover, sets will then have to be represented by structured terms and searched by explicitly-defined recursive procedures:
Program verification
Authors: Hogger Christopher John
Published: November 2023

We have seen that deduction can be applied to logic programs in order either to compute answers to queries (by total evaluation) or to derive new programs (by partial evaluation). In this Theme we look at the use of deduction for showing that programs are correct relative to logic specifications. In this context correctness is taken to be the property whereby, in relation to any query, the answers logically determined by the progam are exactly those logically determined by the specification.

A logic specification is a set S of logic sentences, asserted independently of the program, which defines all the relations named in that program. In general it is both natural and sufficient for each sentence in S defining a relation R to take the propositional form
Use of Sequential Bayes with Class Probability Trees
Authors: Michie D , Attar A Al
Published: November 2023

For building classifiers from data, rule induction has established itself as an alternative to multivariate statistical approaches, including those of ‘neural’ computing. But modern rule-induction algorithms such as CART and C4 have not yet found a fully satisfactory way of discriminating logical from statistical forms of complexity in data. Systems of sequential Bayes rules offer a less ad hoc basis for combining probabilistic with rule-based approaches. In Evidencer, tree-structured rules are linked in a PROSPECTOR-like procedural hierarchy, and updated and processed according to a thresholding regime adapted from Wald’s sequential analysis (1947). The resulting formalism steers a course between the oversimplifications of PROSPECTOR and the complexity of full multi-level Bayes, while retaining precise error bounds on decisions.
Computability
Authors: Hankin Chris
Published: November 2023

A classical application of the A-calculus was in the study of computability. This is the topic of this chapter. Since most computations involve repetitive execution of “code”, fixed points (for encoding recursion) play a fundamental role; we start by reviewing the Fixed Point Theorem and (re-)introducing the concept of a fixed point combinator. Next, rather than add delta rules for constants (see Chapter 3), we explore how constants can be handled in the pure calculus. We introduce several ways of encoding numerals and functions on them. In the third section, we introduce the notion of A-definability- this allows us to relate the A-calculus to other formalisms such as Kleene’s Recursive Functions and Turing Machines. The final section of this chapter discusses the issue of decidability in the A-calculus and we present some undecidable problems.
Introduction
Authors: Laidler Keith J
Published: November 2023

This chapter outlines the problem area which the material in this book addresses, namely, the application of quantitative methods–popularly known as software metrics – to software engineering and the design of system architectures or structures in particular. It is argued that this is of considerable significance because of the potential impact of poor design decisions upon a wide range of quality factors of a system when it is finally implemented. The software engineering background to the book is then described. The chapter concludes with an outline of the structure of the book and a summary of its key points. This book is concerned with quantitative approaches to software engineering, otherwise known as software metrics. Within this rather broad domain the book addresses a particular concern: the production of software system designs. To date, the main thrust of research in software metrics has been towards the measurement of code, yet it is our belief that by the time the code is available for measurement, the majority of a software project’s resources have been committed, so that any strategic changes in direction become prohibitively expensive.
Summary
Authors: Laidler Keith J
Published: November 2023

Here we review the scope of the work described within this book, and summarize its major findings. We proceed to discuss some of the weaknesses of this research and highlight the areas of potential significance which have been uncovered but which have yet to be explored. To recap: this book has been concerned with the development and, even more important, the evaluation of a set of system architecture metrics that might provide the software designer with feedback while making design decisions. This aim has, in turn, generated another aim, which has been the derivation of a method to support the development and evaluation of software metrics in general.
A Generalization of the Least General Generalization
Authors: Arimura H , Shinohara T , Otsuki S , Ishizaka H
Published: November 2023

In this chapter, we present a polynomial time algorithm, called a k-minimal multiple generalization (k-mmg) algorithm, where k ≥ 1, and its application to inductive learning problems. The algorithm is a natural extension of the least general generalization algorithm developed by Plotkin and Reynolds. Given a finite set of ground first-order terms, the k-mmg algorithm generalizes the examples by at most k first-order terms, while Plotkin’s algorithm does so by a single first-order term. We apply the k-mmg algorithm to several learning problems in inductive logic programming, and knowledge discovery in databases.
More Than Meets the Eye: Animal Learning and Knowledge Induction
Authors: Kehoe E J
Published: November 2023

Animals share many of the same learning problems as faced by untutored machine systems. In the ordinary environment, animals must continuously discover associations between potential signals and subsequent events that are crucial to their wellbeing. Moreover, the animals must build this world model from a highly limited training set, without having prior knowledge or verbal instructions. Experiments using conditioned reflex methods have examined issues fundamental to all learning systems. These include: • Credit assignment, e.g., animals capitalize on any sequence of reliable signals for subsequent events. • Representation, e.g., the XOR problem can be solved by animals. • Productivity, e.g., the rate of learning improves across successive problems that are structurally similar but differ in their superficial features. • Anticipation, e.g., conditioned responses are finely timed so that they are neither too early nor too late during a warning signal.
Large Heterogeneous Knowledge Bases
Authors: Tyugu E
Published: November 2023

This chapter discusses large knowledge bases as software development tools which support the creativity of programming in the large. User requirements, architecture and internal knowledge representation language of large knowledge bases are considered. Higher order constraint networks are proposed for representing knowledge about computability.
Recent Progress with BOXES
Authors: Sammut C
Published: November 2023

The Boxes algorithm of Michie and Chambers (1968) has proved to be an effective and flexible method for learning to control dynamic systems. The algorithm, in its original form has been used as a benchmark for many experiments in control tasks such as pole balancing. Recent work in our laboratory has shown that the Boxes algorithm can be improved to yield very good learning rates. We describe experiments on a variety of update functions and discuss their robustness. We also develop the notion of freezing of Boxes, suggested by Miehe and implemented by Bain (1990). We have also been concerned with synthesising a readable account of the control strategy employed by a set of boxes. Some preliminary work has begun in combining decision tree Learning algorithms with Boxes. Using this method, we regard BOXES as the acquirer of sub-cognitive skills and the decision tree induction as a means of introspecting on the learned strategy to generate understandable control rules.
Inductively Speeding Up Logic Programs
Authors: Numao M , Maruoka T , Shimura M
Published: November 2023

This chapter presents a speed-up learning method for logic programs, which accelerates a program by composing macro clauses based on partial structures of proof trees. Many systems have been proposed for composing useful macros, e.g., some of them select macros that connect two peaks in a heuristic function. Another employs heuristics that select useful macros. Although they work well in some domains, such methods depend on domain dependent heuristics that have to be exploited by their users. We propose a heuristic-independent mechanism by detecting backtracking. The method uses a dead-end path as a negative explanation tree, compares it with positive one, and finds a first different node to remove its corresponding rule by composing a macro. Repeated substructures in such a macro are then combined by applying the generalize-number technique and by sharing common substructures. Experimental results in STRIPS domain show that, by selecting an appropriate set of macros, 1) backtracking in solving training examples are suppressed, 2) its problem solving efficiency does not deteriorate even after learning a number of examples, 3) after learning 30 training examples, no backtracking occurs in solving 100 test examples different from the training examples. In conclusion, the proposed method speeds up the problem solving from 10 to 100 times.
Inverting Entailment and Progol
Authors: Muggleton Stephen
Published: November 2023

This paper firstly provides a re-appraisal of the development of techniques for inverting deduction, secondly introduces Mode-Directed Inverse Entailment (MDIE) as a generalisation and enhancement of previous approaches and thirdly describes an implementation of MDIE in the Progol system. Progol is implemented in C and available by anonymous ftp. The re-assessment of previous techniques in terms of inverse entailment leads to new results for learning from positive data and inverting implication between pairs of clauses.
Discovery of Protein Structural Constraints in a Deductive Database using Inductive Logic Programming
Authors: King Ross D , Clark Dominic A , Shirazi Jack , Sternberg Michael J E
Published: November 2023

This paper describes a framework for the use of machine learning as a tool to aid scientists in the discovery of patterns in data. The framework is tested by the application of the inductive logic programming (ILP) program GOLEM to the discovery of constraints in the packing of beta-sheets in alpha/beta proteins. These constraints (rules) play a part in the protein folding problem, an important unsolved problem in molecular biology. Constraints were learnt for four features of beta-sheet packing: the winding direction of two sequential sheets, whether two sequential sheets pack parallel or anti-parallel, whether two sheets pack adjacently, and whether a beta-sheet is at an edge. Investigation of the constraints found revealed interesting patterns, some of which were previously known, others that were novel. Novel features include the discovery that the relationship between pairs of sequential strands is in general one of decreasing size, and that more sequential pairs of strands wind in the direction out than the direction in. We conclude that machine learning has a role for scientists as a pattern discovery tool.
Controlling a Steel Mill with BOXES
Authors: McGarity Michael , Sammut Claude , Clements David
Published: November 2023

We describe an application of the BOXES learning algorithm of Michie and Chambers (1968) to a large-scale, real-world problem, namely, learning to control a steel mill. By applying BOXES to a model of a skinpass mill (a type of steel mill), we find that the BOXES algorithm can be made to produce a robust controller relatively quickly. Various aspects of the BOXES algorithm are adapted for the higher dimensionality and noise present in the skinpass mill. These changes are critically examined to find those which give a better controller.
A Reasoning System for Legal Analogy
Authors: Haraguchi Makoto
Published: November 2023

This paper presents a reasoning system that performs analogical reasoning for legal rules under an order-sorted representation. Analogy is often used in the domain of law to derive an appropriate conclusion for a particular case not covered by any legal rule. For such a case, lawyers are considered to find a legal rule whose requirement is similar to the case with respect to some significant points. Then the rule is analogically applied to the case for which the same or a similar conclusion of the rule is derived.
Kouichi Hirata
Authors: Hirata Kouichi
Published: November 2023

Abduction is a methodology of scientific inquiry. Peirce showed three types of abduction, and expressed them by one syllogism. In computer science, especially in the fields of automated reasoning and machine learning, various researches on abduction or abductive logic have been developed. In order to systematically understand such researches and to clearly discuss abduction, this paper classifies abduction into five types. This new classification is based on an interpretation of the syllogism in abduction and the definitions of hypotheses. We examine various researches on abduction so far developed and show that many researches on abduction can be placed in our classification. Furthermore, we discuss the most essential type of abduction in our classification for logic programming and default logic, and describe Prolog programs for abduction.