Angluin introduced the class of pattern languages as term languages over strings on a finite alphabet, and showed that the class is identifiable in the limit from texts (positive data).III Angluin's definition of pattern languages, erasing substitutions are disallowed.Extended pattern languages are term languages over strings when erasing substitutions are allowed.The question of identifiability in the limit of extended pattern languages from texts has not been resolved, and is one of the outstanding open problems in inductive inference.However, there are at least two subclasses that are known to be identifiable.Shinohara has shown that the the class of extended pattern languages that can be generated by regulx patterns (these are patterns in which each variable occurs no more than once) is identifiable in the limit from texts.Wright showed that the class of extended pattern languages where the pattern contains at most m distinct variables, for any positive integer rn, is identifiable in the limit from texts.The present paper considers a generalisation of regular patterns where each variable occurring in the pattern occurs exactly rn times for some positive integer m.Such patterns arc referred to as quasi-regular patterns, and for each m, the corresponding class of extended pattern languages is denoted QRP,, .It is shown that for each m, the class QRP,, is identifiable in the limit from texts.The proof employs a sophisticated combinatorial argument for bounding the search space.It is also shown that the class U,QRP, is identifiable in the limit from texts.Pcnnission to n&r digital or hard copies of all or part of this work for personal or classroom USC is granted without fee provided that copies are not made or distributed for prolit or con~tnercial advantage and that copies bear this notice and the full citation on thZ first p"ge.-fo copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or SI fw.

An alternating direction implicit (ADI) method which requires the solution of three tridiagonal sets of equations at each time step is suggested for solving the general parabolic equation with variable coefficients in three space dimensions. A sufficient condition for stability is proved in the pure initial value case. Other existing finite difference schemes are mentioned and numerical results are presented.

An alternating direction implicit (A.D.I.) method, which requires the solution of two tridiagonal sets of equations at each time step, is derived for solving a parabolic equation with variable coefficients in two space dimensions with a mixed derivative. The method is shown to be unconditionally stable for two semi-infinite ranges of an auxiliary parameter. Other existing finite difference schemes are mentioned and numerical results are presented.

The alternating direction implicit (A.D.I.) method of the present authors (Mitchell and Fairweather, 1964) is modified and used to solve the nine-point Laplace difference equation in a square. The greater accuracy of the method, h4 as compared with h2 for the Peaceman–Rachford method, where h is the mesh size, is achieved with no appreciable increase in time or effort. The new A.D.I. method is then combined with the Schwarz Alternating Procedure to solve the nine-point difference equation in non-rectangular regions with sides parallel to the co-ordinate axes. Special attention is given to the re-entrant L-shaped region.

Finite-difference solutions are considered for the heat conduction equation in one space dimension subject to general boundary conditions involving linear combinations of the function and its space derivative. It is shown that under such conditions, instability can often arise even although “stable” formulae of the Crank Nicholson type are used. In particular, the persistent error discussed by Parker and Crank (1964) is shown to be a weak case of this more serious instability.

Alternating direction methods of Douglas-Rachford type are considered as a means of solving the biharmonic equation. The family of methods obtained contains the Conte-Dames formula as a special case.

Some new high accuracy quadrature formulae involving derivatives of the integrand are derived and compared with existing formulae.

A method is given for generating systematically difference replacements of the heat condúction equation of any desired order of truncation error. The method is then used to obtain explicit and implicit formulae of high accuracy.