# Technical Reports 2000

## Summary

2000/01 Kohei Honda, Vasco Vasconcelos and Nobuko Yoshida.

Secure Information Flow as Typed Process Behaviour.

2000/02 James Heather, Gavin Lowe and Steve Schneider.

How to Prevent Type Flaw Attacks on Security Protocols

2000/03 Charles Eaton.

On Finite Groups of p- Local Rank One and a Conjecture of Robinson.

2000/04 Andy White, Mike Dampier and Derek Raine.

Radial Infall of a Spinning Particle into a Schwarzschild Black Hole.

2000/05 J.R. Collier, D. McInerney, S. Schnell, P.K. Maini, D.J. Gavaghan, P. Houston and C.D. Stern.

A Cell Cycle Model for Somitogenesis: Mathematical Formulation and Numerical Simulation.

2000/06 Vincent Schmitt.

Applying enriched categories to quasi-uniform spaces.

2000/07 Max Kelly, Anna Labella, Vincent Schmitt and Ross Street.

Categories enriched on two sides.

2000/08 John Hunton.

Complete cohomology theories and the homology of their omega spectra.

2000/09 A. H. Forrest, J. R. Hunton and J. Kellendonk.

Projection Quasicrystals III: Cohomology

2000/10 Michael Hoffmann, Nik Ruskuc and Richard M. Thomas.

Automatic semigroups with subsemigroups of finite Rees index.

2000/11 Anne Kværnø and Ben Leimkuhler.

A time-reversible, regularized, switching integrator for the N-body problem.

2000/12 Ben Leimkuhler and Sebastian Reich.

A Reversible Averaging Integrator for Multiple Time-Scale Dynamics.

2000/13 Kathryn Harriman, David Gavaghan, Paul Houston and Endre Süli.

Adaptive Finite Element Simulation of Currents at Microelectrodes to a Guaranteed Accuracy. An E Reaction at a Channel Microband Electrode.

2000/14 Kathryn Harriman, David Gavaghan, Paul Houston, David Kay and Endre Süli.

Adaptive Finite Element Simulation of Currents at Microelectrodes to a Guaranteed Accuracy. ECE and EC2E Mechanisms at Channel Microband Electrodes.

2000/15 Karin Erdmann, Thorsten Holm and Nicole Snashall.

Twisted bimodules and Hochschild cohomology for self-injective algebras of class An,II.

2000/16 B. M. Brown and M. Marletta.

Spectral inclusion and spectral exactness for singular non-selfadjoint Sturm-Liouville problems.

2000/17 Roger Carter and Robert Marsh.

Regions of linearity, Lusztig cones and canonical basis elements for the quantized enveloping algebra of type A4.

2000/18 Roger Carter and Robert Marsh.

Canonical Bases and Piecewise-linear Combinatorics.

2000/19 John Appleby, Tony Barnard, Robert Marsh, Dave Pountney, Poppy Pickard and David Singmaster.

UMTC 1999 - Teaching Mathematical Concepts Using Puzzles and Games.

2000/20 Neil Ghani, Christoph Lüth and Stefan Kahrs.

Rewriting the Conditions in Conditional Rewriting.

2000/21 R. K. Beatson, W. A. Light and S. Billings.

Fast Solution of the Radial Basis Function Interpolation Equations: Domain Decomposition Methods.

2000/22 Richard L. Gault and Iain A. Stewart.

An infinite hierarchy in a class of polynomial-time program schemes.

2000/23 Michael Hoffmann and Richard M. Thomas.

Automaticity and commutative semigroups.

2000/24 Paul Houston, Christoph Schwab and Endre Süli.

Discontinuous hp-Finite Element Methods for Advection--Diffusion Problems.

2000/25 Gavin Lowe.

Semantic Models for Information Flow.

2000/26 J. Levesley and D.L. Ragozin.

A note on local polynomial approximation on compact manifolds.

2000/27 Michael J. Ward, Darragh McInerney, Paul Houston, David Gavaghan and Philip Maini.

The Dynamics and Pinning of a Spike for a Reaction-Diffusion System.

2000/28 J. Levesley.

Convergence of Euclidean Radial Basis Approximation on Spheres

2000/29 Iain A. Stewart.

Program schemes, queues, the recursive spectrum and zero-one laws.

2000/30 S.J. Hales and J. Levesley.

On Compactly Supported, Positive Definite, Radial Basis Functions

2000/31 P. Houston and E. Suli.

hp-Adaptive Discontinuous Galerkin Finite Element Methods for First-Order Hyperbolic Problems

2000/32 Anna Labella and Vincent Schmitt.

Change of Base, Cauchy-completion and Reversibility

2000/33 Harald Schmid and Christiane Tretter.

Singular Dirac Systems and Sturm-Liouville Problems Nonlinear in the Spectral Parameter

2000/34 Margarita Kraus and Christiane Tretter.

Eigenvalue estimates for the Dirac operator on warped products over bounded manifolds

2000/35 Cristoph Lüth and Neil Ghani.

An Introduction to Categorical Rewriting

2000/36 R. J. Marsh and K. Rietsch.

The intersection of opposed big cells in the real flag variety of type G2.

2000/37 Alan Forrest, John Hunton and Johannes Kellendonk.

Cohomology groups for projection point patterns

2000/38 Alan Forrest, John Hunton and Johannes Kellendonk.

TOPOLOGICAL INVARIANTS FOR PROJECTION METHOD PATTERNS

2000/39 Stephen D. Bond, Brian B. Laird and Benedict J. Leimkuhler.

On the approximation of Feynmankac path integrals for quantum statistical mechanics.

2000/40 Dietrich Kuske.

Distributive lattices with a decidable monadic second order theory

2000/41 Irek Ulidowski and Shoji Yuen.

General Process Languages with Time

2000/42 Marco Marletta and Anton Zettl.

Eigenvalue inequalities for higher order differential operators and Hamiltonian systems

2000/43 Duncan Parkes and Rick Thomas.

Syntactic Monoids and Word Problems

2000/44 Duncan Parkes.

Formal Languages and the Word Problem in Groups

2000/45 Dietrich Kuske.

Towards a language theory for infinite N-free pomsets

2000/46 D. Notbohm.

On the 2-compact group DI(4)

2000/47 D. Notbohm.

A uniqueness result for orthogonal groups as 2-compact groups

2000/48 Colin M Campbell, Edmund F Robertson, Nik Ruskuc and Richard M Thomas.

Automatic completely-simple semigroups

2000/51 Markku Niemenmaa and Richard M Thomas.

Groups, Combinatorics and Computer Science - University of Oulu, August 1999

2000/49 Steffen Koenig.

Blocks of category O, double centralizer properties, and Enright's completions.

2000/50 Th. Brüstle, S. Koenig and V. Mazorchuk.

The coinvariant algebra and representation types of blocks of category O*.

## Full details

2000/01 Kohei Honda, Vasco Vasconcelos and Nobuko Yoshida.

Secure Information Flow as Typed Process Behaviour.

We propose a new type discipline for the pi-calculus in which secure information flow is guaranteed by static type checking. Secrecy levels are assigned to channels and are controlled by subtyping. A behavioural notion of types capturing causality of actions plays an essential role for ensuring safe information flow in diverse interactive behaviours, making the calculus powerful enough to embed known calculi for type-based security. The paper introduces the core part of the calculus, presents its basic syntactic properties, and illustrates its use as a tool for programming language analysis by a sound embedding of a secure multi-threaded imperative calculus of Volpano and Smith. The embedding leads to a practically meaningful extension of their original type discipline. Other fundamental technical elements, culminating in the behavioural non-interference result, are also sketched.

2000/02 James Heather, Gavin Lowe and Steve Schneider.

How to Prevent Type Flaw Attacks on Security Protocols

A type flow attack on a security protocol is an attack where a field that was originally intended to have one type is subsequently interpreted as having another type. A number of type flaw attacks have appeared in the academic literature. In this paper we prove that type flaw attacks can be prevented using a simple technique of tagging each field with some information indicating its intended type.

2000/03 Charles Eaton.

On Finite Groups of p- Local Rank One and a Conjecture of Robinson.

2000/04 Andy White, Mike Dampier and Derek Raine.

Radial Infall of a Spinning Particle into a Schwarzschild Black Hole.

In this paper we investigate the radial infall of a particle with elementary particle spin into a Schwarzschild black hole in a theory with contact torsion. As the particle falls a non-radial intrinsic spin gives a term in the energy momentum tensor, which is not present for a radial pointing spin and which represents the spin contribution to total angular momentum. Thus for a distant observer the Schwarzschild black hole acquires a small rotation.

2000/05 J.R. Collier, D. McInerney, S. Schnell, P.K. Maini, D.J. Gavaghan, P. Houston and C.D. Stern.

A Cell Cycle Model for Somitogenesis: Mathematical Formulation and Numerical Simulation.

After many years of research, the mechanisms that generate a periodic pattern of repeated elements (somites) along the length of the embryonic body axis is still one of the major unresolved problems in developmental biology. Here we present a mathematical formulation of the cell cycle model for somitogenesis proposed in Development 105 (1989), 119--130. We show that the model can indeed account for the spatiotemporal patterning of somite formation during normal development as well as the periodic abnormalities produced by heat shock treatment. We also relate the model to recent molecular data on the process of somite formation.

2000/06 Vincent Schmitt.

Applying enriched categories to quasi-uniform spaces.

The represention of complete metric spaces by enrichments due to F.W. Lawvere is extented to quasi-uniform spaces. Moreover quasi-uniformly continuous maps are described as enriched functors. The quasi-uniform space completion is also viewed as a Cauchy-completion. Super monoidal functors are introduced to obtain these results. A 2-category of enrichments over different bases is defined. In this general context the Cauchy-completion is still a universal construction.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/07 Max Kelly, Anna Labella, Vincent Schmitt and Ross Street.

Categories enriched on two sides.

We introduce morphisms v - w of bicategories, more general than the original ones of Bénabou. When v =1, such a morphism is a category enriched in the bicategory w. Therefore these morphisms can be regarded as categories enriched in bicategories "on two sides". There is a composition of such enriched categories, leading to a simple kind of tricategory Caten whose objects are bicategories. It follows that a morphism from v to w in Caten inducesa 2-functor v-Cat - w-Cat, while an adjunction between v and w in Caten induces one between the 2-categories v-Cat and w-Cat. Left adjoints in Caten are necessarily homomorphisms in the sense of Bénabou, while right adjoints are not. Convolution appears as the internal hom for a monoidal structure on Caten. The 2-cells of Caten are functors; modules can also be defined, and we examine the structures associated with them.

2000/08 John Hunton.

Complete cohomology theories and the homology of their omega spectra.

Suppose Ê is a spectrum obtained by completion of a ring spectrum E at some ideal I of its coefficients E. We study the homology of the omega spectrum spectrum representing Ê and show that the techniques of coalgebraic algebra provide a language enabling a simple description of this homology and of the homological view of the process of completion. Results are obtained for a wide range of connective theories and the main examples of complete Landweber exact theories including that of Morava E theory.

2000/09 A. H. Forrest, J. R. Hunton and J. Kellendonk.

Projection Quasicrystals III: Cohomology

We compute the cohomology of canonical projection tilings of codimension smaller or equal to 3.

2000/10 Michael Hoffmann, Nik Ruskuc and Richard M. Thomas.

Automatic semigroups with subsemigroups of finite Rees index.

The notion of automaticity has been widely studied in groups and some progress has been made in understanding this notion in the wider context of semigroups. The purpose of this paper is to study the connections between the automaticity of semigroups S and T where T is a subsemigroup of finite Rees index in S.

2000/11 Anne Kværnø and Ben Leimkuhler.

A time-reversible, regularized, switching integrator for the N-body problem.

This article describes a gravitational N-body integration algorithm conserving linear and angular momentum and time-reversal symmetry. Forces are dynamically partitioned based on interbody separation, so that the long-range forces are evaluated relatively rarely and close approaches are treated by an efficient regularization technique. The method incorporates an automatic stepsize adjustment based on a Sundman time-transformation. Although the scheme is formally second order, the most intensive computations (the close-approach dynamics) are executed at higher order, thus improving the overall accuracy. Numerical experiments indicate that the method can effectively treat few-body gravitational problems with two- body close approaches, and it compares favorably with other schemes presente in the literature.

2000/12 Ben Leimkuhler and Sebastian Reich.

A Reversible Averaging Integrator for Multiple Time-Scale Dynamics.

This paper describes a new reversible staggered timestepping method for simulating long-term dynamics formulated on two or more timescales. By assuming a partitioning into fast and slow variables, it is possible to design an integrator that (1) averages the force acting on the slow variables over the fast motions and (2) resolves the fast variables on a finer time-scale than the others. The method is described for Hamiltonian systems, but could be adapted to certain types of non-Hamiltonian reversible systems.

2000/13 Kathryn Harriman, David Gavaghan, Paul Houston and Endre Süli.

Adaptive Finite Element Simulation of Currents at Microelectrodes to a Guaranteed Accuracy. An E Reaction at a Channel Microband Electrode.

We extend our earlier work (K. Harriman et al., Electrochem. Commun. 2 (2000) (150) on adaptive finite element methods for disc electrodes to the case of an E reaction mechanism to the increasingly popular channel microband electrode configuration. We use the standard Galerkin finite element method for the diffusion-dominated (low-flow) case, and the streamline diffusion finite element method for the convection- dominated (high-flow) case. We demonstrate excellent agreement with previous approximate analytical results across the range of parameters of interest, on comparatively coarse meshes.

2000/14 Kathryn Harriman, David Gavaghan, Paul Houston, David Kay and Endre Süli.

Adaptive Finite Element Simulation of Currents at Microelectrodes to a Guaranteed Accuracy. ECE and EC2E Mechanisms at Channel Microband Electrodes.

We extend our earlier work on the use of adaptive finite element methods to simulate the current for an E reaction mechanism at a channel microband electrode to the more complex ECE mechanism, and the non-linear EC2E mechanism. We again use the standard Galerkin approach for the diffusion dominated (low-flow) case, and the streamline diffusion finite element method (SDFEM) for convection-dominated (high-flow) case, and compare our results with previous numerical and analytical approximations. We give a general discussion on the implications of our results for numerical simulation at micro-electrodes.

2000/15 Karin Erdmann, Thorsten Holm and Nicole Snashall.

Twisted bimodules and Hochschild cohomology for self-injective algebras of class An,II.

Up to derived equivalence, the representation-finite self-injective algebras of class An are divided into the wreath-like algebras (containing all Brauer tree algebras) and the Moebius algebras. In [Erdmann and Holm "Twisted bimodules and Hochschild cohomology for self-injective algebras of class An", Forum Math. 11 (1999)], the ring structure of Hochschild cohomology of wreath-like algebras was determined, the key observation being that kernels in a minimal bimodule resolution of the algebras are twisted bimodules. In this paper we prove that also for Moebius algebras certain kernels in a minimal bimodule resolution carry the structure of a twisted bimodule. As an application we obtain detailed information on subrings of the Hochschild cohomology rings of Moebius algebras.

2000/16 B. M. Brown and M. Marletta.

Spectral inclusion and spectral exactness for singular non-selfadjoint Sturm-Liouville problems.

We consider the effect of regularization by interval truncation on the spectrum of a singular non-selfadjoint Sturm-Liouville operator. We present results on spectral incluion and spectral exactness for the cases where the singularity is in Sims Case II or Sims Case III. For Sims Case I we present a test for spectral inexactness, which can be used to detect when the interval truncation process is generating spurious eigenvalues. Numerical results illustrate the effectiveness of this test.

2000/17 Roger Carter and Robert Marsh.

Regions of linearity, Lusztig cones and canonical basis elements for the quantized enveloping algebra of type A4.

Let Uq be the quantum group associated to a Lie algebra g of rank n. The negative part U- of U has a canonical basis, defined by Kashiwara and Lusztig, with favourable properties. The approaches of Kashiwara and Lusztig lead to a set of alternative parametrizations of the canonical basis, one for each reduced expression for the longest word in the Weyl group of g. We show that if g is of type A4 there are close relationships between the Lusztig cones, canonical basis elements and the regions of linearity of reparametrization functions arising from the above parametrizations. A graph can be defined on the set of simplicial regions of linearity with respect to adjacency, and we further show that this graph is isomorphic to the graph with vertices given by the reduced expressions of the longest word of the Weyl group modulo commutation and edges given by long braid relations.

Keywords: Quantum group, Lie algebra, Canonical basis, Tight monomials, Weyl group, Piecewise-linear functions.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/18 Roger Carter and Robert Marsh.

Canonical Bases and Piecewise-linear Combinatorics.

Let Uq be the quantum group associated to a Lie algebra g of rank n. The negative part U-q of Uq has a canonical basis, defined by Kashiwara and Lusztig, with favourable properties. The approaches of Lusztig and Kashiwara lead to a set of alternative parametrizations of the canonical basis, one for each reduced expression for the longest word in the Weyl group of g. We describe the authors' recent work establishing close relationships between the Lusztig cones, canonical basis elements and the regions of linearity of reparametrization functions arising from the above parametrizations in type A4 and give some speculations for type An.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/19 John Appleby, Tony Barnard, Robert Marsh, Dave Pountney, Poppy Pickard and David Singmaster.

UMTC 1999 - Teaching Mathematical Concepts Using Puzzles and Games.

This paper explores and suggests ways in which puzzles and games can be used to stimulate and motivate the learning of mathematics. We include a selection of puzzles appropriate for various first year courses in a variety of topics, as well as examples of puzzles suitable for higher level and extended use.

2000/20 Neil Ghani, Christoph Lüth and Stefan Kahrs.

Rewriting the Conditions in Conditional Rewriting.

Category theory has been used to provide a semantics for term rewriting systems at an intermediate level of abstraction between the actual syntax and the relational model. Recently we have developed a semantics for TRSs using monads which generalises the equivalence between algebraic theories and finitary monads on the category Set. This semantics underpins the recent categorical proofs of state-of-the-art results in modular rewriting.

We believe that our methods can be applied to modularity for conditional rewriting where several open problems exist. Any results we achieve here would be highly significant as, for the first time, substantial open problems in rewriting would have been solved using categorial techniques. This paper reports on the first step in this project, namely the construction of a semantics for CTRS using monads.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/21 R. K. Beatson, W. A. Light and S. Billings.

Fast Solution of the Radial Basis Function Interpolation Equations: Domain Decomposition Methods.

In this paper we consider domain decomposition methods for solving the radial basis function interpolation equations. There are three interwoven threads to the paper. The first thread provides good ways of setting up and solving small to medium sized radial basis function interpolation problems. These may occur as subproblems in a domain decomposition solution of a larger interpolation problem. The usual formulation of such a problem can suffer from an unfortunate scale dependence, not intrinsic in the problem itself. This scale dependence occurs for instance when fitting polyharmonic splines in even dimensions.

We present and analyze an alternative formulation, available for all strictly conditionally positive definite basis functions, which does not suffer from this drawback, at least for the very important example previously mentioned. This formulation changes the problem into one involving a strictly positive definite symmetric system, which can be easily and efficiently solved by Cholesky factorisation. The second section shows that a natural domain decomposition method for the interpolation equations can be viewed as an instance of von~Neumann's alternating projection algorithm. Here the underlying Hilbert space is the reproducing kernel Hilbert space induced by the strictly conditionally positive definite basis function. We show that the domain decomposition method presented converges linearly under very weak non- degeneracy conditions on the possibly overlapping subdomains. The last section presents some algorithmic details, and numerical results, of a domain decomposition interpolatory code for polyharmonic splines in 2 and 3 dimensions. This code has solved problems with 5 million centres and can fit splines with 10,000 centres in approximately 7 seconds on very modest hardware.

2000/22 Richard L. Gault and Iain A. Stewart.

An infinite hierarchy in a class of polynomial-time program schemes.

We define a class of program schemes RFDPS constructed around notions of forall-loops, repeat-loops, arrays and if-then-else instructions, and which take finite structures as inputs, and we examine the class of problems, denoted RFDPS also, accepted by such program schemes. The class of program schemes RFDPS is a logic, in Gurevich's sense, in that: every program scheme accepts an isomorphism-closed class of finite structures; we can recursively check whether a given finite structure is accepted by a given program scheme; and we can recursively enumerate the program schemes of RFDPS. We show that the class of problems RFDPS properly contains the class of problems definable in inductive fixed-point logic (for example, the well-known problem Parity is in RFDPS) and that there is a strict, infinite hierarchy of classes of problems within RFDPS (the union of which is RFDPS) parameterized by the depth of nesting of forall-loops in our program schemes. This is the first strict, infinite hierarchy in any polynomial-time logic properly extending inductive fixed-point logic (with the property that the union of the classes in the hierarchy consists of all problems definable in the logic). The fact that there are problems (like Parity) in RFDPS which cannot be defined in many of the more traditional logics of finite model theory (which often have zero-one laws) essentially means that existing tools, techniques and logical hierarchy results are of limited use to us.

2000/23 Michael Hoffmann and Richard M. Thomas.

Automaticity and commutative semigroups.

We give an example of a finitely generated commutative semigroup that is not automatic.

Keywords: Automatic group. Automatic semigroup. Regular language. Commutative semigroup.

2000/24 Paul Houston, Christoph Schwab and Endre Süli.

Discontinuous hp-Finite Element Methods for Advection--Diffusion Problems.

We consider the hp-version of the discontinuous Galerkin finite element method for second-order partial differential equations with nonnegative characteristic form. This class of equations includes second-order elliptic and parabolic equations, first-order hyperbolic equations, as well as problems of mixed hyperbolic-elliptic-parabolic type. Our main concern is the error analysis of the method in the absence of streamline-diffusion stabilization. In the hyperbolic case, an hp-optimal error bound is derived. In the self-adjoint elliptic case, an error bound that is h-optimal and p-suboptimal by 1/2 a power of p is obtained. These estimates are then combined to deduce an error bound in the general case. For element-wise analytic solutions the method exhibits exponential rates of convergence under p-refinement. The theoretical results are illustrated by numerical experiments.

2000/25 Gavin Lowe.

Semantic Models for Information Flow.

In the past several definitions of information flow have been presented, based upon process algebras. Unfortunately, these appear to all be either too weak-failing to identify certain subtle forms of information flow-or too strong-indicating information flow when there is none. In this paper, we produce a definition that aims to overcome these shortcomings. We base our definition that aims to overcome these shortcomings. We base our definition upon an operational model of CSP that reasons about the ways in which nondeterministic choices can be resolved, and so is more discriminating than previous models. Our definition of information flow is then that the behaviour of one agent can have some influence upon another agent's view of the system. This definition gives the expected results on all thought experiments tried to date, and also satisfies certain desirable properties.

2000/26 J. Levesley and D.L. Ragozin.

A note on local polynomial approximation on compact manifolds.

In [LR1] we give a local error estimate for approximation of smooth functions by spherical harmonics. For a k-times differentiable function f we show that there is a spherical polynomial p such that |f(x)-p(x)| <= C rk, for x in Dr, where Dr is a disk of radius r on the sphere. We generalise this result to all compact manifolds in a very elementary way, retaining the essence of the argument used on the sphere.

[LR1] J. Levesley and D.L. Ragozin.
Local approximation on manifolds using radial functions and polynomials. In A. Cohen, C. Rabut and L. Schumaker (editors), Curve and Surface Fitting: Saint Malo 1999, 291-300. Vanderbilt University Press, Nashville (2000).

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/27 Michael J. Ward, Darragh McInerney, Paul Houston, David Gavaghan and Philip Maini.

The Dynamics and Pinning of a Spike for a Reaction-Diffusion System.

The motion of a one-spike solution to a simplified form of the Gierer-Meinhardt activator-inhibitor model is studied in both a one-dimensional and a two-dimensional domain. The pinning effect on the spike motion associated with the presence of spatially varying coefficients in the differential operator, referred to as precursor gradients, is studied in detail. In the one-dimensional case, we derive a differential equation for the trajectory of the spike in the limit E tends to 0, where E is the activator diffusivity. A similar differential equation is derived for the two-dimensional problem in the limit for which E<<1 and D>>1, where D is the inhibitor diffusivity. A numerical finite-element method is presented to track the motion of the spike for the full problem in both one and two dimensions. Finally, the numerical results for the spike motion are compared with corresponding asymptotic results for various examples.

Available as: gzipped PostScript (.ps.gz)

2000/28 J. Levesley.

Convergence of Euclidean Radial Basis Approximation on Spheres

In this paper we investigate the convergence of radial basis interpolation when all of the data lie on a sphere. Here, we use strictly conditionally positive definite radial functions defined in the ambient Euclidean space. These are strictly conditionally positive definite of the same order when restricted to the sphere. The analysis of v. Golitschek and Light [vgl] can then be used to give an error estimate for radial approximation in Euclidean space when the data is restricted to the sphere.

[vgl] M. von Golitschek and W. A. Light.
Interpolation by polynomials and radial basis functions on spheres.. Constr. Approx. (2000). To appear.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/29 Iain A. Stewart.

Program schemes, queues, the recursive spectrum and zero-one laws.

We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ+(1), is such that the class of problems accepted by these program schemes is exactly the class of recursively solvable problems. The class of problems accepted by the program schemes of the class NPSQ(1) where only access to a queue, and not the additional numeric universe, is allowed is exactly the class of recursively solvable problems that are closed under extensions. We define an infinite hierarchy of classes of program schemes for which NPSQ(1) is the first class and the union of the classes of which is the class NPSQ. We show that the class of problems accepted by the program schemes of NPSQ has a zero-one law and is the union of the classes of problems defined by the sentences of all vectorized Lindstroem logics formed using operators whose corresponding problems are recursively solvable and closed under extensions. Finally, we show how our results can be applied to yield logical characterizations of complexity classes and provide logical analogs to a number of inequalities and hypotheses from computational complexity theory involving complexity classes ranging from NP through to ELEMENTARY.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/30 S.J. Hales and J. Levesley.

On Compactly Supported, Positive Definite, Radial Basis Functions

The space dimension in which a radial function $\phi$ is positive definite is characterised by conditions on $\hat \phi(\sqrt{w})$. These can be seen as a natural generalisation of the result of Schoenburg [Sch38]. A relationship is given between the smoothness of compactly supported radial functions and the space dimension wherein they are positive definite.

[Sch38] I. J. Schoenberg.
Metric spaces and completely monotone functions. Ann. Math. no.39 (1938), 811-841.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/31 P. Houston and E. Suli.

hp-Adaptive Discontinuous Galerkin Finite Element Methods for First-Order Hyperbolic Problems

We consider the a posteriori error analysis of hp-discontinuous Galerkin finite element approximations to first-order hyperbolic problems. In particular, we discuss the question of error estimation for linear functionals, such as the outflow flux and the local average of the solution. Based on our a posteriori error bound we design and implement the corresponding adaptive algorithm to ensure reliable and efficient control of the error in the prescribed functional to within a given tolerance. This involves exploiting both local polynomial-degree-variation and local mesh subdivision. The theoretical results are illustrated by a series of numerical experiments.

Available as: gzipped PostScript (.ps.gz)

2000/32 Anna Labella and Vincent Schmitt.

Change of Base, Cauchy-completion and Reversibility

We investigate the effect of the change of base 2-functors V-Cat --> W-Cat induced by two-sided enrichments V --> W on Cauchy-complete objects. We restrict our study to the case of locally posetal bases. Reversibility is defined for locally posetal bicategories, two-sided enrichments and, Cauchy-completion. We show that a reversible left adjoint two-sided enrichment F : V --> W between locally posetal bicategories induces some adjunction F~ -| F~ : V-SkCRcCat --> W-SkCRcCat between sub-categories of skeletal and Cauchy-reversible-complete enrichments. We give two examples of application, sheaves and group actions.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/33 Harald Schmid and Christiane Tretter.

Singular Dirac Systems and Sturm-Liouville Problems Nonlinear in the Spectral Parameter

For the Dirac operator with spherically symmetric potential V:(0,infinity) --> R we investigate the problem whether the boundary points of the essential spectrum are accumulation points of discrete eigenvalues or not. Our main result shows that the accumulation of such eigenvalues is essentially determined by the asymptotic behaviour of V at 0 and infinity. We obtain this result by using a Levinson type theorem for asymptotically diagonal systems depending on some parameter, a comparison theorem for the principal solutions of singular Dirac systems, and some criteria on the eigenvalue accumulation (respectively, non-accumulation) of lambda-nonlinear singular Sturm-Liouville problems.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/34 Margarita Kraus and Christiane Tretter.

Eigenvalue estimates for the Dirac operator on warped products over bounded manifolds

In this paper we consider the Dirac operator DM on manifolds M which are, apart from submanifolds of codimension k+1, warped products where the fibers are k-dimensional spheres. By means of a suitable decomposition of the space of spinors and an abstract operator theoretic result, we show for k>1 that the spectrum of a Dirac operator DM is symmetric with respect to 0 and has a gap around 0. We establish estimates for its eigenvalues, in particular we show that k/(2 fmax) is a lower bound for the first positive eigenvalue where fmax is the maximum value of the warpe function f.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/35 Cristoph Lüth and Neil Ghani.

An Introduction to Categorical Rewriting

Term rewriting systems (TRSs) are widely used throughout computer science as they form an abstract model of computation. However, the concrete syntactic nature of term rewriting often obscures the underlying structure, and the usual semantics based upon relations lacks the structure to adequately model key concepts arising in more complex problems.

A more abstract semantics at an intermediate level of abstraction between the syntax and the relational model is therefore needed. Generalising the categorical treatment of universal algebra, we model TRSs by monads. This way, we have for the first time been able to give categorical proofs of state of the art results in rewriting. This paper forms an introduction to our research, highlighting the new insights afforded by the categorical perspective and sketching the application of this semantics to modular rewriting.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/36 R. J. Marsh and K. Rietsch.

The intersection of opposed big cells in the real flag variety of type G2.

We compute the Euler characteristics of the individual connected components of the intersection of two opposed big cells in the real flag variety of type G2, verifying a conjecture of Rietsch.

Available as: gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)

2000/37 Alan Forrest, John Hunton and Johannes Kellendonk.

Cohomology groups for projection point patterns

Aperiodic point sets (or tilings) which can be obtained by the method of cut and projection from higher dimensional periodic sets play an important role for the description of quasicrystals. Their topological invariants can be computed using the higher dimensional periodic structure. We report on the results obtained in collaboration with A. Forrest and J. Hunton on the cohomology groups of projection point patterns supplemented by explicit calculations made by F. Gähler for many well-known icosahedral tilings.

2000/38 Alan Forrest, John Hunton and Johannes Kellendonk.

TOPOLOGICAL INVARIANTS FOR PROJECTION METHOD PATTERNS

This book is a systematic study of patterns in Euclidean space arising from the so-called projection method. These include the quasiperiodic patterns, but our approach covers also those patterns with arbitrary degrees of periodicity. The main approach starts with the point of view that the patterns give rise to non-commutative spaces in the sense of Connes and hence to topological invariants (K-theory) which reflect the geometric properties of the underlying pattern. These non-commutative spaces are approximated with commutative spaces arising from certain dynamical systems and this yields calculational methods using the tools of homotopy theory. We also show that these invariants provide useful obstruction theories for certain properties of the patterns of interest to quantum mechanics.

The material in this book is ordered as follows. In Chapter I we define and describe the various dynamical systems that can be associated to a projection method pattern, and examine their topological relationships. These are compared with the pattern groupoid and its associated C* algebra in Chapter II where these latter objects are introduced. Also in Chapter II we set up and prove the equivalence of our various topological invariants; we end the chapter by demonstrating how these invariants provide an obstruction to a pattern being self-similar.

The remaining chapters offer three illustrations of the computability of these invariants. In Chapter III we give a complete calculation for all `codimension one' projection patterns -- patterns arising from the projection of slices of Zd+1 to Rd for more or less arbitrary acceptance domains. In Chapter IV we give descriptions of the invariants for generic projection patterns arising from arbitrary projections ZN to Rd but with canonical acceptance domain. Here, applying the result at the end of Chapter II, we prove the result mentioned above that almost all canonical projection method patterns have infinitely generated cohomology and so fail to be substitution tilings. In Chapter V we examine the case of canonical projection method patterns with finitely generated cohomology, such as would arise from a substitution system. We develop a systematic approach to the calculation of these invariants and use this to produce closed formulae for the cohomology and K-theory of projection patterns of codimension 1, 2 and 3: in principle the procedure can be iterated to higher codimensions indefinitely, though in practice the formulae would soon become tiresome. Some parameters of these formulae allow for a simple description in arbitrary codimension, as e.g. the Euler characterisitc (V.2.8). We end with a short description of the results for the Ammann-Kramer tiling, the main tiling used to model physical quasicrystals.

2000/39 Stephen D. Bond, Brian B. Laird and Benedict J. Leimkuhler.

On the approximation of Feynmankac path integrals for quantum statistical mechanics.

2000/40 Dietrich Kuske.

Distributive lattices with a decidable monadic second order theory

The present paper characterizes classes of distributive lattices whose monadic, monadic chain, or monadic antichain theory is decidable.

Available as: gzipped PostScript (.ps.gz)

2000/41 Irek Ulidowski and Shoji Yuen.

General Process Languages with Time

In recent years a large number of process languages with time have been developed as more realistic formalisms for description and reasoning about concurrent systems. We propose a uniform framework, based on the ordered structural operational semantics (OSOS) approach, for extending arbitrary process languages with discrete time. The generality of our framework allows the user to select the most suitable timed process language for a task in hand. This is possible because the user can choose any operators, whether they are standard or new application-specific operators, provided that they preserve a version of weak bisimulation and all processes in the considered language satisfy the time determinacy property. We also propose several constraints on ordered SOS rules for the operators such that some other properties, which reflect the nature of time passage, are satisfied.

2000/42 Marco Marletta and Anton Zettl.

Eigenvalue inequalities for higher order differential operators and Hamiltonian systems

We study eigenvalues of selfadjoint regular 2n-th order differential operators as functions of the boundary conditions and establish inequalities among them. In particular the well known classical inequalities among the Dirichlet, Neuman and periodic eigenvalues in the second order case are extended to order 2n.

2000/43 Duncan Parkes and Rick Thomas.

Syntactic Monoids and Word Problems

The purpose of this paper is to discuss some intriguing connections between group theory and formal language theory. The main topics considered here are syntactic monoids and word problems in groups. We will talk about the extent to which languages can be characterized by their syntactic monoids and relate the theory of syntactic monoids to that of insertions and deletions in languages. We finish off by drawing some of these themes together.

2000/44 Duncan Parkes.

Formal Languages and the Word Problem in Groups

We consider some interactions between the theory of groups and the theory of formal languages.

For any group G and generating set X we shall be primarily concerned with three sets of words over X: the word problem, the reduced word problem and the irreducible word problem.

We explain the relationships between these three sets of words and give necessary and sufficient conditions for a language to be the word problem (or the reduced word problem) of a group.

We prove that the groups which have context-free reduced word problem with respect to some finite monoid generating set are exactly the context-free groups, thus proving a conjecture of Haring-Smith.

We also show that, if a group G has finite irreducible word problem with respect to a monoid generating set X, then the reduced word problem of G with respect to X is simple. In addition, we show that the reduced word problem is recursive (or recursively enumerable) precisely when the word problem is recursive. The irreducible word problem corresponds to the set of words on the left hand side of a special rewriting system which is confluent on the equivalence class containing the identity.

We show that the class of groups which have monoid presentations by means of finite special lambda-confluent string-rewriting systems strictly contains the class of plain groups (the groups which are free products of a finitely generated free group and finitely many finite groups), and that any group which has an infinite cyclic central subgroup can be presented by such a string-rewriting system if and only if it is the direct product of an infinite cyclic group and a finite cyclic group.

Available as: gzipped PostScript (.ps.gz)

2000/45 Dietrich Kuske.

Towards a language theory for infinite N-free pomsets

N-free or series-parallel pomsets are a model for the behavior of modularly constructed concurrent systems. The investigation of languages of finite N-free pomsets was initiated by Lodaya and Weil who extended the theorems by Kleene and by Myhill and Nerode on recognizable word languages to this setting. In this paper, we extend Lodaya and Weil's results to infinite N-free pomsets and generalize Büchi's theorem. Furthermore, we investigate first-order definable, starfree, and aperiodic sets of infinite N-free pomsets and prove results in the spirit of McNaughton and Papert's and Schützenberger's theorems for finite words.

Available as: gzipped PostScript (.ps.gz)

2000/46 D. Notbohm.

On the 2-compact group DI(4)

Besides the simple connected compact Lie groups there exists one further simple connected 2-compact group, constructed by Dwyer and Wilkerson, the group DI(4). The mod-2 cohomology of the associated classifying space BDI(4) realizes the rank 4 mod-2 Dickson invariants. We show that mod-2 cohomology determines the homotopy type of the space BDI(4) and that the maximal torus normalizer determines the isomorphism type of DI(4) as 2-compact group. We also calculate the set of homotopy classes of self maps of BDI(4).

Available as: gzipped PostScript (.ps.gz)

2000/47 D. Notbohm.

A uniqueness result for orthogonal groups as 2-compact groups

Two connected compact Lie groups are isomorphic if and only if their maximal torus normalizers are isomorphic. It is conjectured that this result generalizes to p-compact groups. Here, we prove the generalization for orthogonal groups O(n), the special orthogonal groups SO(2k+1) and the spinor groups Spin(2k+1) considered as 2-compact groups.

Available as: gzipped PostScript (.ps.gz)

2000/48 Colin M Campbell, Edmund F Robertson, Nik Ruskuc and Richard M Thomas.

Automatic completely-simple semigroups

The notion of automaticity has been widely studied in groups and some progress has been made in understanding the notion in the wider context of semigroups. The purpose of this paper is to study automatic completely-simple semigroups. We show that, if S is a completely-simple semigroup M[H; I, J; P] (with I and J finite), then S is automatic if and only if the group H is automatic. As a consequence, we deduce that automatic completely-simple semigroups are finitely presented. We also show that automatic completely-simple semigroups are characterized by the fellow traveller property and also that the existence of an automatic structure is independent of the choice of generating set.

2000/51 Markku Niemenmaa and Richard M Thomas.

Groups, Combinatorics and Computer Science - University of Oulu, August 1999

The conference "Groups, Combinatorics and Computer Science" was held at the University of Oulu in Finland from the 4th to the 9th of August 1999.

This is a record of some of the talks presented at the conference. In addition, the abstracts that were available at the conference and the scheduled programme of talks is included.

The abstracts/talks contained in this report are as follows:

B. Amberg, "Radical rings and products of groups"

C. Campbell, "The semigroup efficiency of groups"

A. Caranti, "Combinatorics of Lie words and graded Lie algebras of maximal class"

P. Csoergoe and M. Niemenmaa, "On loops and groups"

A. Drapal, "Zassenhaus groups and loops"

A. Erfanian, "A problem about comparison on growth sequences of finite simple groups"

G. Havas, "Coset enumeration"

M. Herzog, "On groups in which normality is a transitive relation"

A. Koponen and K. Luosto, "Definability of group theoretic notions"

P. Palfy, "On the isomorphism problem of Cayley graphs"

J. Phillips, "Nonassociative group theory"

G. Rosenberger, "Endliche Tetraedergruppen"

R. Thomas, "Formal languages and group theory"

2000/49 Steffen Koenig.

Blocks of category O, double centralizer properties, and Enright's completions.

2000/50 Th. Brüstle, S. Koenig and V. Mazorchuk.

The coinvariant algebra and representation types of blocks of category O*.

Author: Simon Ambler, tel: 0116 252 3406.