-
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*.
![[University Home]](/images/unihome.gif){kind=small}
![[Faculty of Science]](/images/fac_of_science.gif){kind=small}
![[MCS Home]](/images/schhome.gif){kind=small}
![[University Index A-Z]](/images/index.gif){kind=small}
![[University Search]](/images/search.gif){kind=small}
![[University Help]](/images/help.gif){kind=small}
