CSR 1-99 A Multilevel k-way Partitioning Algorithm for Finite Element Meshes using Competing Ant Colonies
A.E. Langham and P.W. Grant
The self-organizing properties of ant colonies are employed to
tackle the classical combinatorial optimization problem of graph
partitioning. Structural information from the graph is mapped onto an
environment upon which a number of colonies compete for
resources. Using Genetic Programming, a Foraging Strategy is evolved which
when executed by the ants in each colony leads to a restructuring of the
global environment corresponding to a good partition. Multiple
colonies allows for simultaneous k-way partitioning which can provide better
partitions than current algorithms which are based on recursive bisection.
Report Titles
CSR 2-99 Tabular Documentation of Interactive Deterministic Systems derived from Algebraic Models
A.J. Wilder and J.V. Tucker
Many reactive deterministic systems have a simple algebraic model
consisting of a set S of states, a set C of commands the system may
receive and a state transition function n : S x C -> S that can be
extended to operate over streams. We study decompositions of the
state transition function using definition-by-cases organised around
mode sets and system actions. We show how these decompositions
can be documented by tabular displays developed by D. L. Parnas
and coworkers.
We consider how a tree structure can be used to organise such
decompositions and describe how tabular displays are derived by the
use of nesting. By restricting the construction of the tree two special
cases are identified that are useful for decomposing the behaviour of
interactive systems. To illustrate these techniques three examples are
included: a word processor, a pocket calculator and a compact disk
player.
To analyse the tabular displays of the decompositions we analyse the underlying formal model of computation. We consider the
computational power of finite tabular algebraic decompositions and
the problem of determining the completeness and consistency of such
decompositions.
Report Titles
CSR 3-99 Lazy Rewriting on Eager Machinery
Wan Fokkink, Jasper Kamperman and Pum Walters
The article introduces a novel notion of lazy rewriting. By annotating argument positions as lazy, redundant rewrite steps are avoided, and the termination
behaviour of a term rewriting system can be improved. Some transformations of
rewrite rules enable an implementation using the same primitives as an implementation of eager rewriting.
Report Titles
CSR 4-99 Evolving Rules for a SelfÐOrganizing Finite Element Mesh Generation Algorithm
A.E. Langham and P.W. Grant
The self-organizing properties of ant colonies are employed to
tackle the classical combinatorial optimization problem of graph
partitioning. Structural information from the graph is mapped onto an
environment upon which a number of colonies compete for
resources. Using Genetic Programming, a Foraging Strategy is evolved which
when executed by the ants in each colony leads to a restructuring of the
global environment corresponding to a good partition. Multiple
colonies allows for simultaneous k-way partitioning which can provide better
partitions than current algorithms which are based on recursive bisection.
Report Titles
CSR 5-99 An Introduction to Process Algebra
Wan Fokkink
Computer software and network protocols are increasingly important
in daily life. At the same time the complexity of software has rocketed,
so that its correctness is at stake. New methodologies and disciplines
need to be developed, to bring structure to the ever growing jungle of
computer technology. (Semi-)automated manipulation has become an
important means in discovering flaws in software and hardware systems.
Process algebra is a mathematical framework in which system behaviour
is expressed in the form of algebraic terms, enhancing the available
techniques for manipulation.
Concurrency is omnipresent in system behaviour, and in a large part
responsible for its complexity: even very simple behaviours become
wildly complicated when they are executed in parallel. In order to
study programs and protocols in detail, it is imperative that they
are dissected into their concurrent components. Fundamental to process
algebra is a parallel operator, which allows to break down systems
into their concurrent components. A set of equations is imposed that
enables to derive whether behaviours are equivalent. In this framework,
non-trivial properties of systems can be obtained in an elegant fashion.
For example, it may be possible to equate an implementation to the
specification of its required input/output relation. In recent years
a variety of automated tools have been developed to facilitate in
deriving such properties.
Applications of process algebra exist in diverse fields such as
safety critical systems, network protocols, and biology. In the
educational vein, process algebra has been recognised to teach skills
to deal with complex concurrent systems, by representing and reasoning
about such systems in a mathematically clear and precise manner.
Report Titles
CSR 6-99 Structural Operational Semantics
Luca Aceto, Wan Fokkink and Chris Verhoef
Structural operational semantics (SOS) provides a framework to give
semantics to programming and specification languages. In particular,
because of its intuitive appeal and flexibility, SOS has found
considerable application in the study of the semantics of concurrent
processes, where, despite successful work by among others De Bakker,
Zucker, Hennessy, and Abramsky, the methods of denotational semantics
appear to be difficult to apply in general. Recently, SOS has also been
successfully applied as a formal tool to establish results that hold
for classes of process description languages. This has allowed for the
generalization of well-known results in the field of process algebra,
and for the development of a meta-theory for such languages based on
the realization that many of the results in this field only depend
upon general semantic properties of language constructs. The concept
of rule format has played a major role in the development of the
meta-theory of process description languages, and several such formats
have been proposed in the research literature. The principal aim of
this chapter is to introduce the main formats of rules for operational
semantics that have been proposed in the literature, and to show how
they induce operational semantics for process calculi. Each of the
formats surveyed here comes equipped with a rich body of results that
are guaranteed to hold for any process calculus whose operational
semantics is given by rules which satisfy that format. We present some of
these results. In particular, we focus our attention on the
congruence properties of operators specified by the formats we
present, on the connections between SOS semantics and complete proof
systems, on conservative extension results and on the automatic
generation of fully abstract denotational models of process calculi
from the SOS semantics. We also describe a rule format that deals with
variable binders explicitly. Such variable binding mechanisms are
widely used in SOS semantics for, e.g., concurrent and functional
programming languages, the pi-calculus, value passing process
algebras, and in process algebras with recursion.
Report Titles
CSR 7-99 Managing Interactions and Communications in Collaborative Multimedia Applications: The JACIE Way
Abdul S. Haji-Ismail, Min Chen and Phil W. Grant
This paper describes research on the construction
of a development tool for collaborative multimedia
applications. The tool, JACIE (Java-based
Authoring language for Collaborative Interactive Environments),
is a script language which has been developed to
support rapid implementation of a wide range of network-based
interactive and collaborative applications. In particular,
it facilitates the management of interaction and
communication through simple communication primitives
such as channels and interaction protocols, hence hiding
much network programming from programmers.
CSR 8-99 Computation of Free Surface Flows with a Taylor-Galerkin/Pressure-correction Algorithm
V. Ngamaramvaranggul and M.F. Webster
A semi-implicit Taylor Galerkin/pressure-correction finite element
scheme (STGFEM) is developed for problems that manifest free surfaces
associated with the incompressible creeping flow of Newtonian fluids. Such
problems include stick-slip and die-swell flows, both with and without a
superimposed drag flow, and for plane, axisymmetric and annular systems.
The numerical solutions are compared with available analytical and
numerical solutions, both in the neighbourhood of singularities and
elsewhere. Close correspondence in accuracy is extracted to the literature
for both stick-slip and die-swell flows. Stick-slip flow is used as a
precursor study to the more complex free surface calculations involved for
die-swell in extrudate flow. Two different free surface techniques are
reported and results are analysed with mesh refinement and varying
structure.
CSR 9-99 Viscoelastic Multi-mode Simulation of Wire-coating
H. Matallah, P. Townsend and M.F. Webster
A time-stepping finite element method is used to predict the
viscoelastic stresses that arise in a tube-tooling wire-coating problem.
The polymer
melt HDPE is modelled by a multi-mode Phan-Thien/Tanner constitutive
equation. Different flow geometries are considered to address
optimisation
of the process with respect to minimising the stress induced within the
coating produced. The influence of the die itself and the various modes
are considered.
Relaxation times range for a three-mode model from 0.01 to 100s
and for a seven-mode model from 0.001 to 1000s. Typical
Weissenberg numbers may range up to 10,000.
Three modes are sufficient to adequately describe the flow, and
shorter/narrower draw-down regions are identified as being preferable.
Once an adequate land length has been gathered, that has relaxed the
flow stresses prior to draw-down, the actual details of die design are found
to be inconsequential to the induced stresses in the delivered coatings.
CSR 10-99 Simulation of Coatings flows with Slip Effects
V. Ngamaramvaranggul and M.F. Webster
This work is concerned with the numerical prediction of wire
coating flows. Both annular tube-tooling and pressure-tooling type
extrusion-drag flows are investigated for viscous fluids. The effects of
slip at die-walls are analysed and free surfaces are computed. Flow
conditions around the die exit are considered, contrasting imposition of
no-slip and various instances of slip models for die-wall conditions.
Numerical solutions are computed by means of a time-marching Taylor
Galerkin/pressure-correction finite element scheme, that demonstrate how
slip conditions on die walls mitigate stress singularities at die exit.
For pressure-tooling and with appropriate handling of slip, reduction in
shear rate at the die-exit may be achieved. Maximum shear rates for
tube-tooling are about one quarter of those encountered in
pressure-tooling. Equivalently, extension rates peak at land entry, and
tube-tooling values are one third of those observed for pressure-tooling.
With slip and tube-tooling, peak shear values at die-exit may be almost
completely eliminated. Nevertheless, in contrast to the pressure-tooling
scenario, this produces larger peak shear rates upstream within the land
region, than would otherwise be the case for no-slip.
CSR 11-99 Recursive Tables and Effective Definition Schemes
A. J. Wilder
This paper explores the expressive power of algebraic tables via
an adaption of H. Friedman's effective definition schemes (eds). The
separation of tables, for documentation roles, from eds, for a model
of computation, is used to give a clean semantics of algebraic tables
independent of the type of table.
We define (1) the class of recursive algebraic tables and (2) recur-
sive eds. By specialising techniques developed by R. Janicki, we show
how a recursive algebraic table T can be mapped to recursive eds, i.e.
the list of decisions of T . Both operational and denotational semantics
are given for recursive eds and they are shown to agree. The expressive
power of recursive tables is compared to that of while-array program
schemes: both soundness and adequacy are shown.
Report Titles
CSR 12-99 Document Centric Environments: combining the solving and documentation processes
Al Sadiq Ul Amin M. Madani Halepota, Philip W. Grant and Christopher P. Jobling
All disciplines of engineering rely on numerical processing and
visualisation for solving design problems and therefore benefit from support
environments.
These environments should provide a mechanism for integrating different tools
and streamline the process of solving other problems of similar type.
Users can be provided with a consistent interface to the required tool allowing
them to process problem specific data with ease and convenience. One
important source of this convenience could be that the original problem
solver completely documents the process of solving the problem. This is
easier said than done, since the process of documentation is usually seen
as a separate undertaking from the process of obtaining the solution. An
answer to this problem is to combine the process of designing the problem
solution with documentation of the process solution. To do this, a document
centred environment is required which encourages designers to think of the
process of problem solving as an activity, which stems from the process of
documenting. This paper describes such an environment and various aspects of
its realisation. A document paradigm is used from the user-interface of the
environment to its repository. The whole environment is implemented in Java,
with the eXtensible Markup Language (XML) used
to describe the structure of the document. The documents produced by the
environment act as the integrators of tools, which aid in the problem solving
process in various scientific and engineering domains. Two example problems,
one dealing with control system design and other with computational fluid
dynamics are used for illustration.
Report Titles
CSR 13-99 Using Competing Ant Colonies to Solve k-way Partitioning Problems with Foraging and Raiding Strategies
A.E. Langham and P.W. Grant
The self organizing properties of ant colonies are employed to tackle the classical
combinatorial optimization problem of graph partitioning. The graph is mapped onto an
artificial environment in a manner that preserves the structural information. Ants from a number
of colonies compete for resources.
This leads to a restructuring of the global environment corresponding to a good partition.
On the
example graphs, this is shown to outperform the current best algorithms which are based
on recursive bisection techniques.
Report Titles
CSR 14-99 Evolving the Building Activity of a Termite Colony for Finite Element Mesh Generation
A.E. Langham and P.W. Grant
Previous work in swarm intelligence applications has concentrated on combinatorial optimization problems and
is based mainly on the trail laying properties of ant colonies. We tackle a very different kind of problem
involving generation of complex structures. Our method is inspired by work on the building behaviour of social
insects such as wasps and termites. Structures produced are 2-Dimensional triangular meshes which are used to
approximate the solution of fluid flow problems using the finite element method.
We employ a Genetic Algorithm to evolve a set of rules which can be used by a colony of termite-like agents
to mesh an arbitrary domain.
In this approach, meshing is in response to conditions in the local environment, hence changing conditions
can easily be accommodated, making it potentially useful for applications such
as injection moulding where the mesh must 'grow' with the domain.
Report Titles