-
2001/01 S. J. Hales and J. Levesley.
-
Error Estimates For Multilevel Approximation
Using Polyharmonic Splines
Polyharmonic splines are used to interpolate data in a
stationary multilevel iterative refinement scheme. By
using such functions the necessary tools are provided to
obtain simple pointwise error bounds on the approximation.
Linear convergence between levels is shown for regular
data on a scaled multiinteger grid, and a multilevel
domain decomposition method.
Available as:
gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)
-
2001/02 J. Levesley and C. Odell.
-
Evaluation of some Integrals arising from Approximation on Spheres
Integrals arising in approximation on the sphere using radial basis functions in the ambient Euclidean space are computed.
Available as:
gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)
-
2001/03 Edward L. Green, Eduardo N. Marcos and Nicole Snashall.
The Hochschild Cohomology Ring of
a One Point Extension.
-
2001/04 J. Levesley and D. L. Ragozin.
-
Radial basis interpolation on homogeneous manifolds: Convergence rates
Pointwise error estimates for approximation on compact homogeneous manifolds using
dadial kernels are presnted. Tangent space techniques are used to lift the problem from the manifold
to Euclidean space, where methods for proving such error estimates are well established.
Available as:
gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)
-
2001/05 Eric Barthand, Benedict Leimkuhler and Sebastian Reich.
A Test Set for Molecular Dynamics.
-
2001/06 Mariangiola Dezani-Ciancaglini, Paula Severi and Fer-Jan de Vries.
-
Infinitary Lambda Calculus and Discrimination of Berarducci Trees
We propose an extension of lambda calculus for which the
Berarducci trees equality coincides with observational equivalence, when we
observe rootstable or rootactive behavior of terms. In one direction
the proof is an adaptation of the classical Böhm out technique. In
the other direction the proof is based on confluence for strongly
converging reductions in this extension.
Available as:
gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)
-
2001/07
A. Momigliano, S. J. Ambler and R. L. Crole.
-
A Comparison of Formalizations of the
Meta-Theory of a Language with Variable Bindings in Isabelle
Theorem provers can be used to reason formally about programming
languages and there are various general methods for the
formalization of variable binding operators. Hence there are choices
for the style of formalization of such languages, even within a
single theorem prover. The choice of formalization can affect how
easy or difficult it is to do automated reasoning. The aim of this
paper is to compare and contrast three formalizations (termed
de Bruijn, weak HOAS and full HOAS) of a
typical functional programming language. Our contribution is a
detailed report on our formalizations, a survey of related work, and
a final comparative summary, in which we mention a novel approach to
a hybrid de Bruijn/HOAS syntax.
Available as:
gzipped PostScript (.ps.gz)
-
2001/08
Zhiming Liu,
Jifeng He and Xiaoshan Li.
-
Formalizing the Use of UML in Requirement Analysis
The Unified Modelling Language (UML) is now widely used
for modelling a software at different stages: requirement analysis,
design and implementation, during the system development. This work
attempts to develop a method to support the formal use} of UML in
object-oriented software development. The method will include
formal definitions of the modelling units in UML which can be used
to relate the different UML models used at different stages during
software development process. It intends to support step-wised
refinement and component-based development in building models. As a
starting point, this
paper deals with the formalization of the UML models used in the
requirement analysis, i.e. use-case model and conceptual models.
Keywords: Conceptual Model, Use-Case Models, Object-Orientation,
Refinement, UM.
Available as:
gzipped PostScript (.ps.gz)
-
2001/09
Nobuko Yoshida, Martin Berger and Kohei Honda.
-
Strong Normalisation in the Pi-Calculus
We introduce a typed pi-calculus where strong normalisation is
ensured by typability. Strong normalisation is a useful property
in many computational contexts, including distributed
systems. In spite of its simplicity, our type discipline captures a
wide class of converging name-passing interactive behaviour. The proof
of strong normalisability combines methods from typed
lambda-calculi and linear logic with process-theoretic reasoning.
It is adaptable to systems involving state and other
extensions. Strong normalisation is shown to have significant
consequences,
including finite axiomatisation of weak bisimilarity, a fully abstract
embedding of the simply-typed lambda-calculus with products and
sums and basic liveness in interaction.
Strong normalisability has been extensively studied as a
fundamental property in functional calculi, term rewriting and logical
systems. This work is one of the first steps to extend theories and
proof methods for strong normalisability to the context of name-passing
processes.
Available as:
gzipped PostScript (.ps.gz)
-
2001/10 Andrew White.
-
Perturbations of Black Holes in Einstein-Cartan Theory
Torsion is a property of space-time which is not incorporated into the
standard formulation of general relativity but which appears as a
consequence of unification schemes for fundamental forces. It is,
therefore, important to understand its physical consequence. This thesis
begins with an introduction to a non-propagating version of torsion theory
as an extension to general relativity. The theory can be described in terms
of a pair coupled field equations with torsion algebraically linked to
elementary particle spin. In order to develop the theory it is necessary to
postulate a form for the energy-momentum tensor of spinning matter which is
not prescribed in the classical domain. The two main candidates that have
been proposed for spinning fluid are considered. Chapter two contains an
independent reworking of Zerilli's [1] perturbation calculation of a
particle falling into a Schwarzschild black hole. The perturbation
equations are found and the resulting wave equations are derived. The
special case of a particle falling radially is considered in detail.
Chapter three contains new work which employs the method of Zerilli in
torsion theory to consider a particle with spin falling radically into a
black hole. The changes to the black hole are found for each of the two
energy-momentum tensors of Chapter one. This enables us to discount one of
these as unphysical. The differential equations describing the
gravitational radiation released by this system are derived. Finally in
Chapter four these equations are solved to find the gravational radiation
from a spinning particle falling radially. These may be significant for
observational assessments of torsion theory.
-
2001/11 , Zhiming Liu, Xiaoshan Li and Jifeng He.
-
Formalization of the Use-Case Driven Requirement Analysis Process
We have recently proposed a formalization of the use of UML in
requirement analysis. This paper applies that formalization to a
library system as a case study. We intend to show how the approach
supports a use case-driven, step-wised and
incremental development in building models for requirement analysis. The
actual process of building the models shows the importance and feasibility
of the formalization itself.
Available as:
gzipped PostScript (.ps.gz)
-
2001/12 A.A. Arratia and
I.A. Stewart.
-
A note on first-order projections and games
We show how the fact that there is a first-order projection with
successor from the problem TC (transitive closure) to some other
problem Omega enables us to automatically deduce
that a
natural game problem, LG(Omega), whose instances are
labelled instances of Omega, is complete for PSPACE (via
log-space reductions). Our analysis is strongly dependent upon
the reduction from TC to Omega being a logical projection in
that it fails should the reduction be, for example, a log-space
reduction or a quantifier-free first-order translation with
successor.
Available as:
gzipped PostScript (.ps.gz)
-
2001/13 J.R. Kennaway and F.J. de Vries.
-
Infinitary Rewriting
Abstract In this chapter we will give the basic definitions
and properties of infinite terms and infinite reduction
sequences, for both term rewrite systems and the lambda
calculus. We will then study confluence properties in orthogonal
systems, which turns out to be significantly more complicated
than in the finitary case. In general, these systems are only
confluent up to an identification of a certain class of terms. The
breakdown of confluence leads us to consider the concept of a
meaningless term, which further suggests a link with the
lambda-calculus concept of Böhm reduction, and to denotational
semantics for TRSs.
Available as:
gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)
-
2001/14 P. Houston, R. Hartmann and E. Suli.
-
Adaptive Discontinuous Galerkin Finite Element Methods for Compressible Fluid
Flows
Available as:
gzipped PostScript (.ps.gz)
-
2001/15 E. Suli, P. Houston and B. Senior.
-
hp-Discontinuous Galerkin Finite Element Methods for Hyperbolic
Problems: Error Analysis and Adaptivity
Available as:
gzipped PostScript (.ps.gz)
-
2001/16 S. Byun, J.R. Kennaway, V. van Oostrom and F.J. de Vries.
-
Separability and translatability of sequential term
rewrite systems into the lambda calculus
Abstract Orthogonal term rewrite systems do not currently have
any semantics other than syntactically-based ones such as term models
and event structures. For a functional language which
combines lambda calculus with term rewriting, a semantics is most
easily given by translating the rewrite
rules into lambda calculus and then using well-understood
semantics for the lambda calculus. We therefore
study in this paper the question of which classes of TRSs do or do not
have such translations. We
demonstrate by construction that forward branching orthogonal term
rewrite systems are translatable into
the lambda calculus. The translation satisfies some strong properties
concerning preservation of equality and
of some inequalities. We prove that the forward branching systems are
exactly the systems permitting such a
translation which is, in a precise sense, uniform in the right-hand
sides. Connections are drawn between
translatability, sequentiality and separability properties. Simple
syntactic proofs are given of the
non-translatability of a class of TRSs, including Berry's F and
several variants of it.
Available as:
gzipped PostScript (.ps.gz) gzipped DVI (.dvi.gz)
-
2001/17 Manfred Droste and Dietrich Kuske.
-
On random relational structures
Erdös and Rényi gave a probabilistic
construction of the countable universal homogeneous
graph. We extend their result to more general structures
of first order predicate calculus. Our main result shows
that if a class of countable relational structures
contains an infinite omega-categorical universal
homogeneous structure U, then U can be
constructed probabilistically.
Available as:
gzipped PostScript (.ps.gz)
-
2001/18 Antonio Puricella and Iain Stewart.
-
A generic greedy algorithm, partially-ordered graphs and
NP-completeness
Let $\pi$ be any fixed polynomial-time testable, non-trivial,
hereditary property of graphs. Suppose that the vertices of a
graph G are not necessarily linearly ordered but partially
ordered, where we think of this partial order as a collection of
(possibly exponentially many) linear orders in the natural way. We
prove that the problem of deciding whether a lexicographically
first maximal subgraph of G satisfying $\pi$, with respect to
one of these linear orders, contains a specified vertex is NP-complete.
Available as:
gzipped PostScript (.ps.gz)
-
2001/19 Michael Hoffmann.
Automatic Semigroups
-
2001/20 R. Hartmann and P. Houston.
-
Adaptive Discontinuous Galerkin Finite Element Methods
for Nonlinear Hyperbolic Conservation Laws
We consider the a posteriori error analysis
and adaptive mesh design for discontinuous Galerkin finite
element approximations to systems of nonlinear
hyperbolic conservation laws.
In particular, we discuss the question of error estimation for general
linear and nonlinear functionals of the solution; typical examples
include the
outflow flux, local average and pointwise value, as well as the lift
and drag coefficients of a body immersed in an inviscid fluid.
By employing a duality argument, we derive so-called weighted or Type I
a posteriori error bounds; in these error estimates
the element--residuals are multiplied by local weights involving
the solution of a certain dual problem. Based on these a posteriori
bounds, we design and implement the corresponding adaptive algorithm
to ensure efficient and reliable control of the error in the
computed functional. The theoretical results are illustrated by a series of
numerical experiments. In particular, we demonstrate the superiority
of the proposed approach over standard mesh refinement algorithms which employ
ad hoc error indicators.
Available as:
gzipped PostScript (.ps.gz)
-
2001/21 Stephen Hales.
Approximation by Translates of a Radial Basis
Function.
-
2001/22 Alberto Momigliano and Frank Pfenning.
-
Higher-Order Pattern Complement and the Strict
Lambda-Calculus
We address the problem of complementing higher-order
patterns without repetitions of free variables.
Differently from the first-order case, the complement of a
pattern cannot, in general, be described by a pattern, or
even by a finite set of patterns. We therefore generalize
the simply-typed lambda-calculus to include an internal
notion of strict functions so that we can directly express
that a term must depend on a given variable. After fully
developing the basic properties of the strict lambda
calculus, we show that, in this more expressive calculus,
finite sets of patterns without repeated variables are
closed under complement and intersection. Our principal
application is the transformational approach to negation
in higher-order logic programs.
Available as:
gzipped PostScript (.ps.gz)
-
2001/23 Robert Marsh.
-
The Lusztig cones of a quantized enveloping algebra
of type A.
We show that for each reduced expression for the longest
word in the Weyl group of type An, the
corresponding cone arising in Lusztig's description of the
canonical basis in terms of tight monomials is simplicial,
and construct explicit spanning vectors.
-
2001/24 A. A. Baranov and A. E. Zalesskii.
Quasiclassical Lie Algebras.
-
2001/25 A. A. Baranov and A. E. Zalesskii.
Plain representations of Lie Algebras.
-
2001/26 Simon Ambler, Roy Crole and Alberto Momigliano.
-
MERLIN 2001: Mechanized Reasoning
about Languages with Variable Binding
This report contains the papers presented at the
MERLIN 2001 Workshop, which was held in
conjunction with IJCAR 2001, the
International Joint Conference on Automated
Reasoning. MERLIN 2001 took place in Siena,
Italy, on the 18th June 2001, and was organized by the
editors of this volume.
Currently, there is considerable interest in the use of
computers to encode (operational) semantic descriptions of
programming languages. Such encodings are often done
within the metalanguage of a theorem prover or related
system. The encodings may require the use of variable
binding constructs, inductive definitions, coinductive
definitions, and associated schemes of (co)recursion. The
broad aims of MERLIN 2001 were to provide
researchers with a forum to review state of the art
results and techniques, and to present recent and new
progress in the areas of
- the
automation of the metatheory of programming language
semantics, particularly work which involves variable
binding; and
- theoretical and practical problems of
encoding variable binding, especially the representation
of, and reasoning about, datatypes defined from binding
signatures.
Automating variable binding and its associated properties
is notoriously difficult, but such automation pervades the
encoding of programming language semantics. Thus
theoretical methods and practical techniques which
simplify the definition and implementation of such
encodings will prove very useful to the community. We hope
that advances in these areas may well have significance
for the programming language community at large.
The programme committee for MERLIN 2001
was
| Simon Ambler |
(University of Leicester) |
| Roy Crole |
(Chair; University of Leicester) |
| Amy Felty |
(University of Ottawa) |
| Andrew Gordon |
(Microsoft Research, Cambridge) |
| Furio Honsell |
(University of Udine) |
| Tom Melham |
(University of Glasgow) |
| Frank Pfenning |
(Carnegie Mellon University) |
We would like to thank the committee for their input into
all stages of the organization of
MERLIN 2001, but especially that of
reviewing the paper submissions. We are very grateful to
everyone for the time they devoted to this workshop. We
would also like to thank Dieter Hutter, IJCAR Workshop
Chair, and Fabio Massacci, IJCAR Conference Chair, who
have put enormous efforts into the organization of all of
the IJCAR Workshops. Finally we thank the authors,
participants, and others who have contributed to
MERLIN 2001.
-
2001/27 Yifeng Chen.
Generic Compositions.
-
2001/28 Yifeng Chen and J. W. Sanders.
-
Logic of global synchrony
An intermediate-level specification notation is presented for use with BSP-style programming. It is achieved by extending pre-post semantics to reveal state at points of global synchronisation. That enables us to integrate the pre-post, finite and reactive-process styles of specification in BSP, as shown by our treatment of the dining philosophers. The language is provided with a complete set of laws and has been formulated to benefit from a simple predicative semantics.
-
2001/29 Yifeng Chen.
Fixpoints of Non-monotonic Functions.
-
2001/30 R.L. Gault and I.A. Stewart.
-
On a
hierarchy involving transitive closure logic and existential
second-order quantification
We study a hierarchy of logics where each formula of each
logic in the hierarchy consists of a formula of a certain
fragment of transitive closure logic prefixed with an
existentially quantified tuple of unary relation
symbols. By playing an Ehrenfeucht-Fraïssé game
specifically developed for our logics, we prove that there
are problems definable in the second level of our
hierarchy that are not definable in the first; and that if
we are to prove that the hierarchy is proper in its
entirety (or even that the third level does not collapse
to the second) then we shall require substantially
different constructions than those used previously to show
that the hierarchy is indeed proper in the absence of the
existentially quantified second-order symbols.
Available as:
gzipped PostScript (.ps.gz)
-
2001/31 Anne Henke and Steffen Koenig.
Relating polynomial GL(n)-representations
in different degrees.
-
2001/32 L. Greenberg and M. Marletta.
-
The Ekman flow and related problems: spectral
theory and numerical analysis
We consider singular block operator problems of the type
arising in the study of stability of the Ekman boundary
layer. The essential spectrum is located, and an analysis
of the L2 solutions of a related first
order system of differential equations allows the
development of a Titchmarsh-Weyl coefficient
M(lambda). This, in turn, permits a rigorous
analysis of the convergence of approximations to the
spectrum arising from regular problems. Numerical results
illustrate the theory.
Available as:
gzipped PostScript (.ps.gz)
-
2001/33 Martin Edjvet, James Howie, Gerhard Rosenberger and Richard M. Thomas.
-
Finite generalized tetrahedron groups with a
high-power relator
An ``ordinary'' tetrahedron group is a group with a
presentation of the form
<x, y, z : xe1 =
ye2 = ze3 =
(xy-1) f1 =
(yz-1) f2 =
(zx-1) f3 = 1
>
where ei >= 2 and fi
>= 2 for each i. Following Vinberg, we call
groups defined by a presentations of the form
x, y, z : xe1 =
ye2 = ze3 =
R1(x, y) f1 =
R2(y, z) f2 =
R3(z, x) f3 = 1>
where each Ri(a, b) is a cyclically
reduced word involving both a and b,
generalized tetrahedron groups. These groups
appear in many contexts, not least as subgroups of
generalized triangle groups. In this paper, we build on
previous work to start on a complete classification as
to which generalized tetrahedron groups are finite; here
we treat the case where at least one of the
fi is greater than three.
-
2001/34 Jeremy Levesley.
-
Good Point/Bad Point Iterations for Solving the Thin-Plate
Spline Iterpolation Equations.
Preconditioned methods for solving the thin--plate spline
interpolation equations are disadvantaged by data points at which it is difficult to construct almost Lagrange functions. Here we give an algorithm which separates such bad points from the remaining good points, and iterates to convergence, solving on the good points using some iterative method, and solving on the small set of bad points directly. Numerical results are given demonstrating the
effectiveness of this method.
-
2001/35 Antonio Puricella and Iain A. Stewart.
-
Greedy algorithms, H-colourings and a
complexity-theoretic dichotomy
Let H be a fixed undirected graph. An
H-colouring of an undirected graph G is a
homomorphism from G to H. If the vertices of
G are partially ordered then a generic greedy
algorithm computes all lexicographically first maximal
H-colourable subgraphs of G. We show that
the complexity of deciding whether a given vertex of
G is in a lexicographically first maximal
H-colourable subgraph of G is NP-complete,
if H is bipartite, and
Sigma2p-complete, if H
is non-bipartite. This result complements Hell and
Nesetril's seminal result that the basic
H-colouring problem is in P, if H is
bipartite, and NP-complete, if H is non-bipartite.
Our proofs use the basic techniques established by Hell
and Nesetril, combinatorially adapted to our scenario.
-
2001/36 Dietrich Kuske.
-
Another step towards a theory of regular MSC
languages
This paper resumes the study of regular sets of Message
Sequence Charts initiated by Henriksen, Mukund, Narayan
Kumar, and Thiagarajan
[HMKT99]. Differently from their results,
we consider infinite MSCs. It is shown that for bounded
sets of infinite MSCs, the notions of recognizability,
axiomatizability in monadic second order logic, and
acceptance by a deterministic Message Passing Automaton
with Muller acceptance condition coincide. We furthermore
characterize the expressive power of first order logic and
of its extension by modulo-counting quantifiers over
bounded infinite MSCs.
- [HMKT99] J.G. Henriksen, M. Mukund, K. Narayan Kumar and P.S. Thiagarajan.
-
Towards a theory of regular MSC languages, Technical report BRICS RS-99-52 (1999).
Available as:
gzipped PostScript (.ps.gz)
-
2001/37 P. Houston, M. Jensen and E. Suli.
-
hp-Discontinuous Galerkin Finite Element Methods
with Least-Squares Stabilization
We consider a family of hp-version discontinuous Galerkin
finite element methods with least-squares stabilization
for symmetric systems of first-order partial differential
equations. The family includes the classical discontinuous
Galerkin finite element method, with and without
streamline-diffusion stabilization, as well as the
discontinuous version of the Galerkin least-squares finite
element method. An hp-optimal error bound is derived in
the associated DG-norm. If the solution of the problem is
elementwise analytic, an exponential rate of convergence
under p-refinement is proved. We perform numerical
experiments both to illustrate the theoretical results and
to compare the various methods within the family.
Available as:
gzipped PostScript (.ps.gz)
-
2001/38 Yifeng Chen.
-
A Fixpoint Theory for Non-Monotonic Parallelism
This paper studies parallel recursions. The specification
language used in this paper incorporates sequentiality,
nondeterminism, general recursion, reactiveness (including
infinite behaviours) and parallelism. The language is the minimum
of its kind and thus provides a context in which we can study
recursions in general. In order to use Tarski's theorem to
determine the fixpoints of recursions, we need to identify a
well-founded partial order. The bottom of the order corresponds
to the empty loop, whose most appropriate denotation should be
the specification containing all nonterminating behaviours. The
Egli-Milner order has such a bottom. However, conjunctive
parallel composition is not Egli-Milner monotonic. A theorem of
this paper shows that in fact no partial order makes all
recursions in the language monotonic. Tarski's theorem alone is
not enough to determine the fixpoints of all recursions.
Instead of using Tarski's theorem directly, we reason about the
fixpoints of terminating and nonterminating behaviours
separately. Such reasoning is supported by the laws of a new
composition called partition. We propose a fixpoint
technique called the partitioned fixpoint, which is the
least fixpoint of the nonterminating behaviours after the
terminating behaviours reach their greatest fixpoint. The
surprising result is that although a recursion may not be
priority-order monotonic, it must have the partitioned fixpoint,
which is equal to the least priority-order fixpoint. Since the
partitioned fixpoint is well defined in any complete lattice, the
results are applicable to various semantic models. The existing
fixpoint techniques simply become special cases of the
partitioned fixpoint. For example, an Egli-Milner-monotonic
recursion has its least Egli-Milner fixpoint, which can be shown
to be the same as the partitioned fixpoint. The new technique is
more general than the least Egli-Milner fixpoint in that the
partitioned fixpoint can be determined even when a recursion is
not Egli-Milner monotonic. Examples of non-monotonic recursions are
studied. Their partitioned fixpoints are shown to be
consistent with our intuitions.
-
2001/39 Jifeng He, Zhiming Liu and Xiaoshan Li.
-
A Relational Model for Object-Oriented Programming
This report presents a semantics for an object-oriented language with
classes, visibility, dynamic binding, mutual recursive methods and recursion. Our semantic framework identifies both class declarations and commands as designs.
All the programming constructs of our language, such as assignment,
conditional, composition and recursion,
are defined in the exactly same way as their counterparts in the
imperative programming languages.
This makes
the approach more accessible to users who are already familiar with
imperative program design and also enables the use of
existing tools and methods of verification and refinement developed
for these languages.
Furthermore, the algebraic
laws developed for the imperative languages remain applicable in
designing object-oriented programs.
-
2001/40 David J. Green, John R. Hunton and Bjorn Schuster.
-
Chromatic characteristic classes in ordinary group
cohomology
We study a family of subrings, indexed by the natural numbers, of the mod p
cohomology of a finite group G. These subrings are based on a family of
$v_n$-periodic complex oriented cohomology theories and are constructed as
rings of generalised characteristic classes. We identify the varieties
associated to these subrings in terms of colimits over categories of
elementary abelian subgroups of G, naturally interpolating between the work
of Quillen on Var{H^*(BG)}, the variety of the whole cohomology ring, and
that of Green and Leary on the variety of the Chern subring, Var{Ch(G)}.
Our subrings give rise to a 'chromatic' (co)filtration, which has both
topological and algebraic definitions, of \Var{H^*(BG)}
whose final quotient is the variety Var{Ch(G)}.
-
2001/41 S. Schnell, P.K. Maini, D. McInerney, D.J. Gavaghan and P. Houston.
-
Models for Pattern Formation in Somitogenesis: a
Marriage of Cellular and Molecular Biology
Somitogenesis, the process by which a bilaterally
symmetric pattern of cell aggregations is laid down in a
cranio-caudal sequence in early vertebrate development,
provides an excellent model study for the coupling of
interactions at the molecular and cellular level. We
extend a recent chemical pre-pattern model based on the
cell cycle, by including cell movement and show that the
resultant model exhibits the correct spatio-temporal
dynamics of cell aggregation. We also postulate a model to
account for the recently observed spatio-temporal dynamics
at the molecular level.
Available as:
gzipped PostScript (.ps.gz)
-
2001/42 Florent Madelaine and Iain A. Stewart.
-
On the complexity of homomorphism problems involving unary functions.
We show that the uniform constraint satisfaction problem where
instances consist of pairs of unary functions (and an instance is
a yes-instance if there is a homomorphism from the first function
to the second function) can be solved in logspace. We also show
that any analogous non-uniform problem is L-complete if the
(fixed) template function does not contain a fixed point;
otherwise it consists of all unary functions. There is a
significant jump in complexity when we consider constraint
satisfaction problems where the instances are pairs of pairs of
unary functions: the uniform problem can trivially be solved in
NP and we show that there exist non-uniform problems that
are NP-complete.
.
-
2001/43 L. Greenberg and M. Marletta.
-
The counting function for a lambda-rational Sturm-Liouville problem
We develop an oscillation theory for an equation of Hain-Lust type,
valid both outside and inside the essential spectrum. The results proved
allow us to locate eigenvalues in the essential spectrum or resonances
close to the essential spectrum (see Lifschitz). The numerical
implementation of the oscillation theory requires a regularizing transformation
of
Niessen and Zettl.
-
2001/44 Dietrich Notbohm.
-
Homology decompositions for p-compact groups
We construct a homotopy theoretic setup for homology decompositions of classifying spaces of compact Lie groups, which also applies in the context of there homotopy theoretic generalizations, the so called p-compact groups. This setup is then used to show that the existence of the Dwyer-Wilkerson centralizer decomposition with respect to the family of elementary abelian $p$-subgroups of a compact Lie group $G$ or a $p$-compact group $X$ is equivalent to the existence of a subgroup decomposition for $G$ or $X$ with respect to any family of $p$-toral subgroups which contains the radical subgroups of $X$. This generalises and reproves homology decomposition results of Jackowski, McClure and Oliver obtained for compact Lie groups.
-
2001/45 S. Yang.
-
A New Genetic Algorithm Based on Primal-Dual Chromosomes for
Royal Road Functions
Genetic algorithms (GAs) have been broadly studied by a huge amount of researchers and there have been many variations developed based on Holland's simple genetic algorithm (SGA). Inspired by the phenomenon of diploid genotype and dominance mechanism that broadly exist in nature, in this paper we propose a new genetic algorithm --- primal-dual genetic algorithm (PDGA). PDGA operates on a pair of chromosomes that are primal-dual to each other through the
primal-dual mapping, which works in the sense of Hamming distance in genotype. The primal-dual mapping improves the exploration capacity of PDGA and thus
its searching efficiency in the search space. We compare the performance of PDGA over SGA based on the Royal Road functions, which are especially designed for testing GA's performance. The experiment results show that PDGA outperforms SGA for different performance measures.
Available as:
gzipped PostScript (.ps.gz)
-
2001/46 David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatash Raman and S. Srinivasa Rao.
-
Representing Trees of Higher Degree
This paper focuses on space efficient representations of trees that permit basic navigation in constant time. While most of the
previous work has focused on binary trees, we turn our attention to
trees of higher degree. We consider both cardinal trees (rooted
trees where each node has k positions, each of which may have a
reference to a child) and ordinal trees (the children of each node
are simply ordered). Our representations use a number of bits close
to the information theoretic lower bound and support operations in
constant time. For ordinal trees we support the operations of
finding the degree, parent, i'th child and subtree size. For
cardinal trees the structure also supports finding the
child labeled i of a given node apart from the ordinal tree
operations. These operations also provide a mapping from the n
nodes of the tree onto the integers {1,....,n}.
-
2001/47 E. L. Green and N. Snashall.
-
Projective Bimodule Resolutions of an Algebra and Vanishing of the Second Hochschild Cohomology Group
In this paper we construct explicitly the first terms in the minimal projective bimodule resolution of a finite-dimensional algebra from the
minimal right resolution of each of the simple modules. This result is used
to give vanishing results for HH2 of a finite-dimensional algebra, and in particular shows that HH2 = 0 for all Mobius algebras, with the exception of the preprojective algebra of type A3.
-
2001/48 Nobuko Yoshida, Kohei Honda and Martin Berger.
-
Linearity and Bisimulation
Exploiting linear type structure, we introduce a new theory of weak bisimularity for the pi-calculus in which we abstract away not only tau-actions but also non-tau actions which do not affect well-typed observers. This gives a congruence far larger than the standard bisimilarity while retaining semantic soundness. The framework is smoothly extendible to other settings involving nondeterminism and state. As an application we develop a behavioural theory of secrecy in the pi-calculus which ensures secure information flow for a strictly greater set of processes than the type-based approach in [Honda et al. 99, Honda and Yoshida 02], while still offering compositional verification techniques.
-
2001/49 Michael Hoffman, Dietrich Kuske and Richard M. Thomas.
-
Some relatives of automatic and hyperbolic groups
Automatic and hyperbolic groups are well-studied classes. They share the
property that the multiplication can be described in terms of computing
devices. The theory of automatic groups has been extended to automatic
monoids. In this paper we consider also hyperbolic, asynchronously
automatic and rational monoids. The main goal is to determine the
relationships between these classes. In doing so, we prove some new closure
properties of the classes of asynchronously automatic and hyperbolic
monoids.
-
2001/50 Edward L. Green, Nicole Snashall and Oeyvind Soldberg.
-
The Hochschild Cohomology Ring of a Selfinjective Algebra of Finite Representation Type
This paper describes the Hochschild cohomology ring of a selfinjective algebra $\Lambda$ of finite representation type over an algebraically closed field $K$, showing that the quotient $\HH^*{\mathcal N}$, and is thus finitely generated as an algebra.
-
2001/51 Michael Hoffman and Richard M. Thomas.
-
Notions of automaticity in semigroups
We will investigate various possible notions of automaticity in semigroups.
We point out that it makes a difference which side we choose for
multiplication by generators and also which side we pad pairs of strings of
unequal length (unlike the situation in groups, where the different choices
give rise to equivalent definitions) and we investigate the properties of
semigroups satisfying these definitions.
-
2001/52 John Hunton and Bjorn Schuster.
-
Subalgebras of group cohomology defined by infinite loop spaces
We study natural subalgebras $Ch_E(G)$ of group cohomology defined in terms
of infinite loop spaces E and give representation theoretic descriptions of
those based on $QS^0$ and the Johnson-Wilson theories E(n). We describe the
subalgebras arising from the Brown-Peterson spectra BP and as a result give
a simple reproof of Yagita's theorem that the image of $BP^*(BG)$ in
$H^*(BG;F_p)$ is $F$-isomorphic to the whole cohomology ring; the same result
is shown to hold with BP replaced by any complex oriented theory E with a
map of ring spectra $E\rightarrow H F_p$ which is non-trivial in homotopy. We
also extend the constructions to define subalgebras of $H^*(X;F_p)$ for any
space X; when X is finite we show that the subalgebras $Ch_{E(n)}(X)$
give a natural unstable chromatic filtration of $H^*(X;F_p)$.
-
2001/53 Martin Bendersky and John Hunton.
-
On the coalgebraic ring and Bousfield-Kan spectral sequence
for a Landweber exact spectrum
We construct a Bousfield-Kan (unstable Adams) spectral sequence based on
an arbitrary (and not necessarily connective) ring spectrum E with unit and
which is related to the homotopy groups of a certain unstable E completion
of a space X. For E an S-algebra this completion agrees with that of the
first author and R. Thompson. We also establish in detail the Hopf algebra
structure of the
unstable cooperations (the coalgebraic module) $E_*(E_*)$ for an arbitrary
Landweber exact spectrum E, extending work of the second author with M.
Hopkins and with P. Turner and giving basis-free descriptions of the
modules of primitives and indecomposables. Taken together, these results
enable us to give a simple description ofthe $E_2$-page of the E-theory
Bousfield-Kan spectral sequence when E is any Landweber exact ring spectrum
with unit. This extends work of the first author and others and gives a
tractable unstable
Adams spectral sequence based on a $v_n$-periodic theory for all n.}
-
2001/54 Tomasz Radzik and Shengxiang Yang.
-
Experimental evaluation of algorithmic solutions for the maximum
generalised network flow problem
The maximum generalised network flow problem is to maximise the net flow
into a specified
node in a network with capacities and gain-loss factors associated with
edges. In practice,
input instances of this problem are usually solved using general-purpose
linear programming
codes, but this may change because a number of specialised combinatorial
generalised-flow
algorithms have been recently proposed. To complement the known
theoretical analyses of these
algorithms, we develop their implementations and investigate their
actual performance. We
focus in this study on Goldfarb, Jin and Orlin's excess-scaling
algorithm and Tardos and
Wayne's push-relabel algorithm. We develop variants of these algorithms
to improve their
practical efficiency. We compare the performance of our implementations
with implementations
of simple, but non-polynomial, combinatorial algorithms proposed by Onaga and Truemper, and
with performance of CPLEX, a commercial general-purpose linear
programming package.
Available as:
gzipped PostScript (.ps.gz)
![[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}
