-
2002/01 D. Kuske and M. Lohrey.
-
On the theory of one-step rewriting
in trace monoids
We introduce a general class of rewriting systems over
trace monoids, called scattered rewriting systems, which
generalize trace rewriting systems. We prove that the
first-order theory of the one-step rewriting relation
associated with a scattered rewriting system is decidable
but in general not elementary. This extends known results
on semi-Thue systems but our proofs use new methods; these
new methods yield the decidability of local properties
expressed in first-order logic augmented by
modulo-counting quantifiers. Using the main decidability
result, we define several subclasses of trace rewriting
systems for which the confluence problem is decidable.
Available as:
gzipped PostScript (.ps.gz)
-
2002/02 Duncan W. Parkes and Richard M. Thomas.
-
Groups with context-free reduced word problem
In this report we consider reduced word problems of groups. We explain the
relationship between the word problem and the reduced word problem, and we
give necessary and sufficient conditions for a language to be the word
problem (or the reduced word problem) of a group. In addition, we show that
the reduced word problem is recursive (or recursively enumerable) precisely
when the word problem is recursive.
We then prove that the groups which have context-free reduced word problem
with respect to some finite momoid 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; this is a generalization of one direction of a
theorem of Haring-Smith.
-
2002/03 A. Henke and A. Regev.
-
Weyl Modules for the Schur Algebra of the Alternating Group
Let $F$ be the field of complex numbers and $V=V_0 \oplus V_1$ a vector
space over $F$ with $\dim V_0 =\dim V_1$. The symmetric group acts on
$V^{\otimes n}$ by the sign-permutation action. Let $S^*(V,n) \subset
S^*_A(V,n)$ be the corresponding Schur algebras of $S_n$
and of $A_n \subset S_n$ respectively where $A_n$ is the alternating group.
Following the fundamental work of H.~Weyl, the explicit decomposition of
$V^{\otimes n}$ as an $S^*(V,n)$-module was given in work by Berele and
Regev. By appylying the character theory and the representation
theory of $A_n$ we give here the explicit decomposition of $V^{\otimes n}$
as an $S^*_A(V,n)$-module.
-
2002/04 P. Houston, I. Perugia and D. Schotzau.
-
hp-DGFEM for Maxwell's equations
We propose hp-version interior penalty
discontinuous Galerkin methods for the discretization
of the curl-curl operator with divergence free constraint,
often encountered in electromagnetic problems.
For unstructured meshes with hanging nodes,
we present error estimates that are optimal in the meshsize h
and slightly suboptimal in the polynomial
approximation order p.
The performance of these methods is numerically
tested for two-dimensional model problems.
Available as:
gzipped PostScript (.ps.gz)
-
2002/05 R. Hartmann and P. Houston.
-
Goal-Oriented A Posteriori Error Estimation for Compressible Fluid Flows
We consider so-called `goal-oriented' a posteriori error estimation
for discontinuous Galerkin finite element approximations
to the compressible Euler equations of gas dynamics.
By employing a hyperbolic duality argument,
we derive weighted, or Type I, a posteriori error estimates
which bound the error measured in terms of certain
target functionals of real or physical interest.
The practical advantages of this general approach
are illustrated by a series of
numerical experiments.
Available as:
gzipped PostScript (.ps.gz)
-
2002/06 P. Houston, B. Senior and E. Suli.
-
Sobolev Regularity Estimation for hp-Adaptive Finite Element Methods
In this paper we develop an
algorithm for estimating the local Sobolev regularity index of
a given function by monitoring the decay rate of its
Legendre expansion coefficients. On the basis of these local
regularities, we design and implement an hp-adaptive finite
element method based on employing discontinuous piecewise polynomials,
for the approximation of nonlinear systems
of hyperbolic conservation laws.
The performance of the proposed adaptive strategy is demonstrated
numerically.
Available as:
gzipped PostScript (.ps.gz)
-
2002/07 R. Hartmann and P. Houston.
-
Adaptive Discontinuous Galerkin Finite Element Methods for the Compressible
Euler Equations.
In this paper a recently developed approach
for the design of
adaptive discontinuous Galerkin finite element approximations
is applied to physically relevant problems arising in inviscid compressible
fluid flows governed by the
Euler equations of gas dynamics. In particular, we employ so-called
weighted or Type I a posteriori error bounds to drive adaptive
finite element algorithms for the estimation of
the error measured in terms of general linear and nonlinear target
functionals of the solution; typical examples considered here include
the point evaluation of a component of the solution vector, and the
drag and lift coefficients of a body immersed in an inviscid fluid.
This general approach leads to the design of economical finite element meshes specifically tailored to the computation
of the target functional of interest, as well as providing reliable and
efficient error estimation. Indeed, the superiority of the proposed
approach over standard mesh refinement algorithms which employ
ad hoc error indicators will be illustrated by a series of
numerical experiments; here, we consider
transonic flow through a nozzle, as well as subsonic, transonic and
supersonic flows around different airfoil geometries.
Available as:
gzipped PostScript (.ps.gz)
-
2002/08 E. Suli and P. Houston.
-
Adaptive Finite Element Approximation of Hyperbolic Problems.
We review some recent developments concerning the
a posteriori error analysis
of h- and hp-version finite element approximations to hyperbolic problems.
The error bounds stem from an error representation formula which equates the
error in an output functional of interest to the
inner product of the finite element residual with the solution
of a dual (adjoint) problem whose data is the density
function of the target functional. Type I a posteriori error
bounds are derived which, unlike the cruder Type II bounds,
retain the dual solution in the bound as a local
weight-function. The relevance of Type I a posteriori bounds is
argued by showing that the local size of the error
in a hyperbolic problem may be only very weakly correlated to
the local size of the residual; consequently, adaptive refinement algorithms
based on the size of the local residual alone can
be ineffective. The sharpness of Type I a posteriori error bounds
is demonstrated on both structured and adaptively refined meshes.
Available as:
gzipped PostScript (.ps.gz)
-
2002/09 Yifeng Chen and Zhiming Liu.
-
Unifying Temporal Logics
In this paper, we use a technique called {\em generic composition}
to unify temporal logics. Predicates are treated as sets. Temporal
operators are defined as functions, and their axioms become
consequent laws. The underlying semantics of this approach
corresponds to Kripke's relational semantics and is closely
related to logic. Calculational reasoning involving different
temporal logics is supported. It turns out that the modalities of
possibility and necessity become generic composition and its
inverse of converse respectively. Transformers between temporal
logics also become modalities. Various temporal domains are
unified under a concept called {\em resource cumulation}. Generic
composition provides high-level constructions and laws for the
reasoning of temporal operators. Its completeness theorem
guarantees that generic composition and its inverse have the same
expressiveness as the first-order logic.
-
2002/10 A. Baranov.
-
Finitary Lie algebras
An algebra is called finitary if it consists of finite-rank transformations of
a vector space. We classify finitary simple and finitary irreducible Lie
algebras over an algebraically closed field of characteristic different
from 2 and 3.
-
2002/11 Irek Ulidowski and Shoji Yuen.
-
Process Languages for Rooted Weak Preorders
We present a general class of process languages for rooted eager bisimulation
preorder and prove its congruence result. Also,
we present classes of process languages for the rooted
versions of several other weak preorders.
The process languages we propose are defined by the {\em Ordered\/} SOS method
which
combines the traditional SOS approach, based on transition rules, with the
{\em ordering\/}
on transition rules. This new feature specifies the order of application of
rules
when deriving transitions of process terms. We support and illustrate our
results
with examples of process operators and process languages which benefit from the
OSOS
formulation.
-
2002/12 A. Henke and A. Regev.
-
A-Codimensions and A-Cocharacters
The codimensions and the cocharacters of a p.i.algebra arise from the
group algebra FS_n of the symmetric group S_n, where F is an
algebraically closed field of characteristic zero. The subalgebra
FA_n of the alternating subgroup A_n gives rise to the corresponding
A-codimensions and A-cocharacters. Some general properties of these
invariants are studied. In particular, the A-codimensions and the
A-cocharacters of the infinite dimensional Grassmann (exterior) algebra
E are calculated.
-
2002/13 I. A. Stewart.
-
The complexity of achievement and maintenance problems in agent-based systems
We completely classify the computational complexity of the
basic achievement and maintenance agent design problems in bounded
environments when these problems are parameterized by the number of
environment states and the number of agent actions. The different
problems are P-complete, NP-complete, co-NP-complete or PSPACE-complete
(when they are not trivial). We also consider alternative achievement
and maintenance agent design problems by allowing longer runs in
environments (that is, our environments are bounded but the bounds are
more liberal than was the case previously). Again, we obtain a complete
classification but so that the different problems are DEXPTIME-complete,
NEXPTIME-complete, co-NEXPTIME-complete or NEXPSPACE-complete (when they
are not trivial).
-
2002/14 Heinz Langer, Matthias Langer and Christiane Tretter.
-
Variational principles for eigenvalues of block operator matrices
In this paper variational principles for block operator matrices
are established which are based on functionals associated with the
quadratic numerical range and which allow to characterize, e.g.,
eigenvalues in gaps of the essential spectrum.
-
2002/15 Catharina Stroppel.
-
Category O : Gradings and Translation Functors
In this article we consider a grader version of category O. We reprove some results of an article of Beilinson, Ginzburg and Soergel using a different approach. Furthermore, we define a graded version of translation functors and duality. This provides the construction of various graded modules. On the other hand we describe how to get modules which are not 'gradable'.
-
2002/16 Rajeev Raman, Venkatesh Raman and S. Srinivasa Rao.
-
Succinct Indexable Dictionaries with
Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
We consider the {\it indexable dictionary\/} problem which consists in
storing a set $S \subseteq \{0,\ldots,m-1\}$ for some integer $m$,
while supporting the operations of $\Rank(x)$, which returns the
number of elements in $S$ that are less than $x$ if $x \in S$, and
$-1$ otherwise; and $\Select(i)$ which returns the $i$-th
smallest element in $S$.
We give a structure that supports both operations in $O(1)$ time on
the RAM model and requires ${\cal B}(n,m) + o(n) + O(\lg \lg m)$ bits
to store a set of size $n$, where ${\cal B}(n,m) = \ceil{\lg {m
\choose n}}$ is the minimum number of bits required to store any
$n$-element subset from a universe of size $m$. Previous dictionaries
taking this space only supported (yes/no) membership queries in $O(1)$
time. In the cell probe model we can remove the $O(\lg \lg m)$
additive term in the space bound, answering a question raised by Fich
and Miltersen, and Pagh. We present several applications of our
dictionary structure including:
\begin{itemize}
\item an information-theoretically optimal representation for {\it
$k$-ary cardinal trees\/} (aka $k$-ary tries) that uses
${\cal C}(n,k) + o(n+ \lg k)$ bits to store a $k$-ary tree with $n$
nodes and can support parent, $i$-th child, child labeled $i$, and the
degree of a node in constant time, where ${\cal C}(n,k)$ is the
minimum number of bits to store any $n$-node $k$-ary tree. Previous
space efficient representations for cardinal $k$-ary trees required
${\cal C}(n,k) + \Omega(n)$ bits;
\item a representation for multisets where (appropriate
generalisations of) the $\Select$ and $\Rank$ operations can be
supported in $O(1)$ time. Our structure uses ${\cal B}(n, m+n) + o(n)
+ O(\lg \lg m)$ bits to represent a multiset of size $n$ from an $m$
element set; the first term is the minimum number of bits required to
represent such a multiset.
\end{itemize}
We also highlight two other results that may prove
to be useful subroutines in developing succinct data structures:
\begin{itemize}
\item We give a representation of a sequence of $m$ bits, of which $n$
are 1s, % consisting of $n$ 1s and $m-n$ 0s, that uses
${\cal B}(n,m) + o(n)$ bits whenever $m = O(n \sqrt{\lg n})$, and
answers the following queries in constant time: given a position
$i$ in the bit-vector, to report the number of $0$s (or $1$s)
before position $i$ in the bit-vector and given a number $i$, to
return the position of the $i$-th 0 (or 1) in the bit-vector.
This generalises results by Clark and by Pagh.
\item
we give a representation of a sequence of $n$ non-negative
(or strictly positive) integers summing up to an integer $m$
in ${\cal B}(n, m+n) + o(n)$ bits (or ${\cal B}(n,m) + o(n)$
bits respectively), to support partial sum queries in constant
time; in each case the first term is the minimum number of
bits required to represent the partial sums. This is more
space-efficient than related results by Grossi and Vitter,
Tarjan and Yao, Pagh, and Hagerup and Tholey.
\end{itemize}
-
2002/17 Jeremy Levesley.
-
Multilevel Scattered Data Approximation by Adaptive Domain Decomposition
A new multilevel approximation scheme for scattered data is proposed. The scheme relies on an adaptive domain decomposition strategy using quadtree techniques (and their higher-dimensional generalizations). It is shown in the numerical examples that the new method achieves an improvement on the approximation quality of previous well-established multilevel interpolation schemes.
-
2002/18 Jeremy Levesley.
-
Estimates of n-Widths of Sobolev's Classes on Compact Globally Symmetric Spaces of Rank 1
Estimates of Kolmogorov's and linear $n$-widths of Sobolev's classes on compact globally symmetric spaces of rank 1 (i.e. on $S^{d}$, $P^{d}(\RR)$, $P^{d}(\CC)$, $P^{d}(\HH)$, $P^{16}({\rm Cay})$ ) are established. It is shown that these estimates have sharp orders in different important cases. New estimates for the $(p,q)$-norms of multiplier operators $\Lambda = \{\lambda_{k}\}_{k \in \NN}$ are given. We apply our results to get sharp orders of the best polynomial approximations and $n$--widths.
-
2002/20 Nobuko Yoshida.
-
Type-Based Liveness Guarantee in the Presence of Nontermination and Nondeterminism
This paper investigates a type-based framework to guarantee a basic
liveness property in the pi-calculus. The resulting liveness
property ensures that the action at a specified channel will
eventually fire, in spite of the presence of nondeterminism and
possibly diverging computation. We first integrate nontermination into the linear pi-calculus introduced in [Yoshida, Berger and Honda 01],
for which we prove the liveness by a translation into the linear
pi-calculus, preserving a specific sequence of typed actions.
We then extend the calculus with the first-order state, and
prove the liveness property via a translation into the linear
pi-calculus
with nondeterministic sums.
The systematic method based on techniques from term rewriting
systems and analysis of operational structures associated with
linearity leads to a clean proof of the liveness. The liveness
property is interesting not only in its own right, but also in its
nontrivial semantic consequences, including decidability of equations
and non-interference theorems of secure functional and imperative
programming languages.
-
2002/21 Irek Ulidowski.
-
Termination and confluence of term rewrite systems for GSOS process languages
We consider the procedures for automatic derivation of axiom systems and term rewrite systems for process language in the GSOS format. We show that, for a decidable subclass of GSOS process languages, namely syntactically well-founded and linear GSOS process languages, the generated term rewrite systems are strongly normalising, confluent, and sound and complete for bisimulation modulo the associativity and commutativity of the choice operator on closed terms.
-
2002/22 Jose Luis Vivas and Nobuko Yoshida.
-
Dynamic Channel Screening in the Higher Order Pi-Calculus
Recently programming languages have been designed to support mobile
code, i.e. higher-order code that is transferred from a remote
location or domain and executed within the local environment. This may
expose the internal interfaces and objects within a location to
attacks by mobile code. In this work, we propose an extension of
notations based on the Higher-Order Pi-calculus with a primitive
operator whose role is to protect internal interfaces by dynamically
restricting the visibility of channels. The usefulness of these
operators is illustrated by applications involving resource access
control. We show how restrictions on the behaviour of processes based
on the notion of process type, and intended to be checked statically,
can be enforced dynamically with the aid of the filter operator.
-
2002/23 Matthias Langer and David Eschwe.
-
Variational principles for eigenvalues of self-adjoint pencils of
unbounded operators
Variational principles for eigenvalues of certain pencils of unbounded self-adjoint operators $T(\lambda)$ are proved. A generalised Rayleigh functional is used that assigns to a vector $x$ a zero of the function $(T(\lambda)x,x)$, where it is assumed that there exists at most one zero. Since there need not exist a zero for all $x$, an index shift occurs. Using this variational principle, eigenvalues of linear and quadratic pencils and eigenvalues of block operator matrices in a gap of the essential spectrum are characterised. Moreover, applications are given to an elliptic eigenvalue
problem with degenerate weight, Dirac operators, strings in a medium with a viscous friction, and a Sturm--Liouville problem that is rational in the eigenvalue parameter.
-
2002/24 Zhiming Liu, Xiaoshan Li and Jifeng He.
-
Using Transition Systems to Unify UML Requirement Models
The Unified Modeling Language (UML) is the de-facto standard
modeling language for the development of software with broad
ranges of applications. It supports for modeling a software at
different stages during its development: requirement analysis,
design and implementation. The use of UML encourages software
developers to devote more effort on requirement analysis and
modeling to produce better software products. The most important
models to produce in an object-oriented requirement analysis are
a conceptual class model and a use-case model. This
paper proposes a method to combine these two models by using a
classic transition system. Then we can reason about and
refine such systems with well established methods and tools.
Keywords: Object-orientation, UML, Conceptual Model,
Use-Case Model, Object-Orientation, Transition Systems
-
2002/25 Torben Hagerup and Rajeev Raman.
-
An Efficient Quasidictionary
We define a quasidictionary to be a data
structure that supports the following operations:
checkin(v) inserts a data item v
and returns a positive integer tag to be used in future
references to v; checkout(x) deletes
the data item with tag x; access(x)$
inspects and/or modifies the data item with tag $x$. A
quasidictionary is similar to a dictionary, the difference
being that the names identifying data items are chosen by
the data structure rather than by its user. We describe a
deterministic quasidictionary that executes the operations
checkin and access in constant time and
checkout in constant amortized time, works in
linear space, and uses only tags bounded by the maximum
number of data items stored simultaneously in the
quasidictionary since it was last empty.
Available as:
gzipped PostScript (.ps.gz)
-
2002/26 Danny Krizanc, Flaminia L. Luccio and Rajeev Raman.
-
Compact Routing Schemes for Dynamic Ring Networks
We consider the problem of routing in
an asynchronous dynamically changing ring of processors
using schemes that minimize the storage space for the routing
information. In general, applying static techniques to a dynamic
network would require significant re-computation. Moreover, the
known dynamic techniques applied to the ring lead to inefficient schemes.
In this paper we introduce a new technique, Dynamic Interval Routing,
and we show tradeoffs between
the stretch, the adaptation cost and the size of
the update messages used by routing schemes based upon it.
We give three algorithms for rings of maximum size $N$: the first two
are deterministic,
one with adaptation cost zero but stretch $\frac{N}{2}$,
the other with adaptation cost $O(N)$ messages of $O( \log N)$
bits and stretch 1. The third algorithm
is randomized,
uses update messages of size $O(k \log N)$, has adaptation cost $O(k)$ and
expected stretch $1+\frac{1}{k}$, for any
$k \geq 1$.
All schemes require $O(\log N)$ bits per node for
the routing information and all messages headers are of $O(\log N)$ bits.
Available as:
gzipped PostScript (.ps.gz)
-
2002/27 Paula Severi and Femke van Raamsdonk.
-
Eliminating proofs from programs
This paper presents a step in the development of an operational approach to program extraction in type theory. In order to get a program from a lambda-term, the logical parts need to be removed. This is done by a new reduction relation, called
epsilon-reduction. We study the combination of beta-reduction and epsilon-reduction, both in the setting of simply typed lambda-calculus and for
pure type systems. In the general setting the properties confluence, subject reduction, and strong normalization are studied.
Available as:
gzipped PostScript (.ps.gz)
-
2002/28 Paula Severi and Fer-Jan de Vries.
-
An Extensional Bohm Model
We show the existence of an infinitary confluent and normalising extension of the finite extensional lambda calculus with beta and eta. Besides infinite beta reductions also infinite eta reductions are possible in this extension, and terms without head normal form can be reduced to bottom. As corollaries we obtain a simple, syntax based construction of an extensional Bohm model of the finite lambda calculus; and a simple, syntax based proof that two lambda terms have the same semantics in this model if and only if they have the same eta-Bohm tree if and only if they are observationally equivalent wrt to beta normal forms.
The confluence proof reduces confluence of beta, bottom and eta via infinitary
commutation and postponement arguments to confluence of beta and bottom and confluence of eta.
We give counterexamples against confluence of similar extensions based on the identification of the terms without weak head normal form and the terms without top normal form (rootactive terms) respectively.
Available as:
gzipped PostScript (.ps.gz)
-
2002/29 Paula Severi and Fer-Jan de Vries.
-
A lambda calculus for D-infinity
We define an extension of lambda calculus which is fully abstract for Scott's D-infinity models. We do so by constructing an infinitary lambda calculus which not only has the confluence property, but also is normalising: every term has its inf-eta-Bohm tree as unique normal form.
The extension incorporates a strengthened form of eta-reduction besides infinite terms, infinite reductions and a bottom rule allowing to replace terms without head normal form by bottom. The new eta-reduction is the key idea of this paper. It allows us to capture in a compact and natural way Barendregt's complex infinite eta-operation on Bohm trees.
As a corollary we obtain a new congruence proof for Bohm tree equivalence modulo infinite eta-expansion.
Available as:
gzipped PostScript (.ps.gz)
-
2002/30 Irek Ulidowski.
-
Priority rewrite systems for OSOS process languages
We propose a procedure that allows the user to derive automatically a priority rewrite system for an arbitrary process language in the OSOS format. The rewriting of terms within the derived rewrite systems is sound for bisimulation. We show that, for a decidable subclass of OSOS process languages, namely syntactically well-founded and linear OSOS process languages, the derived property rewrite systems are strongly normalising, confluent and complete for bisimulation for closed terms modulo associativity and commutativity of the CCS choice operator +.
-
2002/31 Robert Marsh, Markus Reineke and Andrei Zelevinsky.
-
Generalized associahedra via quiver representations
We provide a quiver-theoretic interpretation of certain smooth complete simplicial fans associated to arbitrary finite root systems in recent work of S. Fomin and A. Zelevinsky. The main properties of these fans then become easy consequences of the known facts about tilting modules due to K. Bongartz, D. Happel and C. M. Ringel.
Available as:
gzipped PostScript (.ps.gz)
-
2002/32 Ralf Hartmann and Paul Houston.
-
Goal-Oriented A Posteriori Error Estimation for Multiple Target Functionals
Available as:
gzipped PostScript (.ps.gz)
-
2002/33 Kathryn Harriman, Paul Houston, Bill Senior and Endre Suli.
-
hp-Version Discontinuous Galerkin Methods with Interior Penalty for
Partial Differential Equations with Nonnegative Characteristic Form
In this paper we consider the a posteriori and a priori error analysis of hp-discontinuous Galerkin interior penalty methods for second-order partial differential equations with nonnegative characteristic form. In particular, we discuss the question of error estimation for linear target 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)
-
2002/34 A. K. Kushpel, J. Levesley and S. Tozoni.
-
Estimates of $n$--Widths of Besov Classes on Two-Point Homogeneous Manifolds
Estimates of Kolmogorov and linear $n$-widths of Besov classes on compact globally symmetric spaces of rank 1 (i.e. on $S^{d}$, $P^{d}(\RR)$, $P^{d}(\CC)$, $P^{d}(\HH)$,
$P^{16}({\rm Cay})$ ) are established. It is shown that these estimates have sharp orders in different important cases. A new characterisation of Besov spaces is also given.
-
2002/35 Rachel Taillefer.
-
Injective Hopf bimodules, cohomologies of infinite dimensional Hopf algebras and graded-commutativity of the Yoneda product
We prove that the category of Hopf bimodules over any Hopf algebra has enough injectives, which enables us to extend some results on the unification of Hopf bimodule cohomologies of \cite{Ta,Ta2} to the infinite dimensional case. We also prove that the cup-product defined on these cohomologies is graded-commutative.
Available as:
gzipped PostScript (.ps.gz)
-
2002/36 A. Henke and S. Doty.
-
Decomposition of tensor products of modular irreducibles for SL_2
We use tilting modules to study the structure of the tensor product of two simple modules for the algebraic group SL_2, in positive characteristic, obtaining a twisted tensor product theorem for its indecomposable direct summands. Various other related results are obtained, and numerous examples are computed.
-
2002/37 Dietrich Kuske and Markus Lohrey.
-
Decidable Theories of Graphs, Factorized Unfoldings and
Cayley-graphs
We show that a connected graph of bounded degree whose automorphism
group has only finitely many orbits is context-free whenever its
monadic second-order theory is decidable. This amounts to the
converse of a result by Muller and Schupp.
We introduce the factorized unfolding of a relational structure that
is a quotient of the unfolding considered by Walukiewicz. We show
that the first-order theory of this factorized unfolding can be
reduced to the first-order theory of the underlying structure. This
result is analogous to Walukiewicz's result who considered the
monadic second-order theories of the unfolding, but differently from
his automata-theoretic proof, we use methods from model theory.
Finally, we apply these results to Cayley-graphs of groups and
monoids and show: the first-order theory of the Cayley-graph of a
group is decidable if and only if the word problem of the group is
decidable. The monadic second-order theory of the Cayley-graph of a
group is decidable if and only if the group is context-free (the
implication ``$\Leftarrow$'' was shown by Muller and Schupp). The
class of monoids whose Cayley-graph has a decidable first-order
(monadic second-order, resp.) theory is closed under arbitrary graph
products (free products, resp.).
-
2002/38 Manfred Droste and Dietrich Kuske.
-
Skew and infinitary formal power series
We investigate finite-state systems with costs. Departing from the
classical theory, in this paper the cost of an action does not only
depend on the state of the system, but also on the time when it is
executed; this reflects the usual human evaluation practices in
which later events are considered less urgent and carry less weight
than close events. We first characterize the terminating behaviors
of such systems in terms of rational formal power series. This
generalizes a classical result of Sch\"utzenberger.
Secondly, we deal with nonterminating behaviors and their costs.
This includes an extension of the B\"uchi-acceptance condition from
finite automata to weigh\-ted automata and provides a characterization
of these nonterminating behaviors in terms of $\omega$-rational
formal power series. This generalizes a classical theorem of
B\"uchi.
-
2002/39 Dietrich Notbohm and Nitu Kitchloo.
-
Quasi finite loop spaces are manifolds
It is an old conjecture, that finite $H$-spaces are
homotopy equivalent to manifolds. Here we prove that this conjecture
is true for loop spaces. Actually, we show that every quasi finite
loop space
is equivalent to
a stably parallelizable manifold. The proof is conceptual and relies on
the theory of p-compact groups.
-
2002/40 Dietrich Notbohm.
-
2-compact groups of rank 2
The concept of p-compact groups is the homotopy theoretic
generalization of the concept of compact Lie groups.
For p=2, we will give a complete list
of all connected 2-compact groups of rank 2.
-
2002/41 R. Marsh and M. Reineke.
-
Canonical basis linearity regions arising from quiver
representations
In this paper we show that there is a link between the combinatorics
of the canonical basis of a quantized enveloping algebra
and the monomial bases of the second author arising from
representations of quivers. We prove that some
reparametrization functions of the canonical basis,
arising from the link between Lusztig's approach to the
canonical basis and the string parametrization of the
canonical basis, are given on a large region of linearity
by linear functions arising from these monomial bases for
a quantized enveloping algebra.
Keywords : Quantum groups, Lie algebra, canonical basis,
parametrization functions, monomial basis, representations
of quivers, degenerations, piecewise-linear functions.
-
2002/42 Steve Lakin.
-
Context-sensitive decision problems in groups (PhD thesis)
The seemingly distinct areas of group theory, formal language
theory, and complexity theory interact in an important way
when one considers decision problems in groups, such as
the question of whether a word in the generators of the
group represents the identity or not. In general, these
problems are known to be undecidable. Much work has been
done on the solvability of these problems in certain
groups, however less has been done on the resource bounds
needed to solve them, in particular with regard to space
considerations. The focus of the work presented here is
that of groups with (deterministic) context-sensitive
decision problems, that is those that have such problems
decidable in (deterministic) linear space. A
classification of such groups (similarly to the way that
the groups with, for example, regular or context-free word
problem,have been classified) seems untenable at
present. However, we present a series of interesting
results with regard to such groups, with the intention
that this will lead to a better understanding of this
area. Amongst these results, we emphasise the difficulty
of the conjugacy problem by showing that a group may have
unsolvable conjugacy problem, even if it has a subgroup of
finite index with context-sensitive conjugacy problem.Our
main result eliminates the previously-considered
possibility that the groups with context-sensitive
word problem could be classified as the set of groups
which are subgroups of automatic groups, by constructing a
group with context-sensitive word problem with is not a
subgroup of an automatic group. We also consider a range
of other issues in this area, in an attempt to increase
the understanding of the sort of groups under consideration.
Available as:
gzipped PostScript (.ps.gz)
-
2002/43 Steffen Koenig, Katsunori Sanada and Nicole Snashall.
-
On Hochschild Cohomology of Orders
We show that certain tiled $R$-orders $\Lambda$ have periodic projective resolutions and hence we determine the Hochschild cohomology ring of $\Lambda$. This generalises, reproves and connects several results in the literature.
-
2002/44 J. Levesley, C. Odell and D. L. Ragozin.
-
Variational Interpolation on Homogeneous Manifolds: the Norming Set Approach
In this paper we follow the norming set approach of Jetter et. al. [1] to
produce error
estimates for invariant kernel interpolation on compact homogeneous manifolds.
For the
sphere cases the results are compared to those of the v. Golitschek and Light
[2]. References :
[1] K. Jetter, J. St\"ockler, and J. D. Ward, Error estimates for scattered
data
interpolation on spheres, {\sl Math. Comp.} {\bf 68} (1999), 733--747.
[2] M. Von Golitschek, and W. A. Light,
Interpolation by polynomials and radial basis functions on spheres, {\sl
Constr.
Approx.} {\bf 17} (2001), 1--18.
-
2002/45 Paul Houston, Ilaria Perugia and Dominik Schotzau.
-
Mixed discontinuous Galerkin approximation of the Maxwell operator
We introduce and analyze a discontinuous Galerkin
discretization of the Maxwell operator in mixed form.
Here, all the unknowns of the underlying system of partial differential
equations are approximated by discontinuous finite element spaces of the
same order.
For piecewise constant coefficients, the method is shown to
be stable and optimally convergent with respect to the mesh size.
Numerical experiments highlighting the performance of the proposed method
for problems with both smooth and singular analytical solutions are
presented.
Available as:
gzipped PostScript (.ps.gz)
-
2002/46 E.L.Green, Nicole Snashall and R.Taillefer.
-
Drinfel'd Double of Taft Algebras
-
2002/47 A. Momigliano and S. J. Ambler.
-
Multi-Level Meta-Reasoning with Higher-Order Abstract Syntax
Combining Higher Order Abstract Syntax (HOAS) and (co)-induction is
well known to be problematic. In previous work~\cite{Ambler02} we have
described the implementation of a tool called Hybrid, within Isabelle
HOL, which allows object logics to be represented using HOAS, and
reasoned about using tactical theorem proving and principles of
(co)induction. Moreover, it is definitional, which guarantees
consistency within a classical type theory. In this paper we describe
how to use it in a multi-level reasoning fashion, similar in spirit to
other meta-logics such $\foldn$ and \emph{Twelf}. By explicitly
referencing provability, we solve the problem of reasoning by
(co)induction in presence of non-stratifiable hypothetical judgments,
which allow very elegant and succinct specifications. We demonstrate
the method by formally verifying the correctness of a compiler for (a
fragment) of Mini-ML, following~\cite{Hannan92lics}. To further
exhibit the flexibility of our system, we modify the target language
with a notion of non-well-founded closure, inspired by Milner &
Tofte~\cite{milner91d} and formally verify via coinduction a subject
reduction theorem for this modified language.
Available as:
gzipped PostScript (.ps.gz)
-
2002/48 Nicole Snashall and Oeyvind Solberg.
-
Support Varieties and Hochschild Cohomology Rings
We define a support variety for a finitely generated module over an artin
algebra $\Lambda$ over a commutative artinian ring $k$, with $\Lambda$
flat as a module over $k$, in terms of the maximal ideal spectrum of the
algebra $\HH^*(\Lambda)$ of $\Lambda$. This is modelled on what is done in
modular representation theory, and the varieties defined in this way are
shown to have many of the same properties as for group rings. In fact the
notion of a variety in our sense and for principal and non-principal
blocks are related by a finite surjective map of varieties. For a finite
dimensional selfinjective algebra over a field the variety is shown to be
an invariant of the stable component of the Auslander-Reiten quiver.
Moreover we give information on nilpotent elements in $\HH^*(\Lambda)$,
give a thorough discussion of the ring $\HH^*(\Lambda)$ on a class of
Nakayama algebras, a brief discussion on a possible notion of complexity
and make a comparison with support varieties for complete intersections.
-
2002/49 Jose Luiz Fiadeiro.
-
Coordination Technologies for Just-In-Time Integration
Whereas the emphasis of research in "Formal Methods" has been mainly
directed to help developers in taming the complexity of constructing
new systems, the challenge today is on evolution, namely on endowing
system components with agility in responding to change and
dynamically procuring collaborations from which global properties of
the system can emerge. As a result, we are running the risk of
building a new generation of legacy systems: systems in which
interactions are too tightly coupled and rigid to operate in
application environments that are "time critical", for instance those
that make use of Web Services, B2B, P2P or operate in what is known
as "internet-time". We suggest, and demonstrate, that support for
"agility" can be found in what we call "coordination technologies" -
a set of analysis techniques, modelling primitives, design principles
and patterns that we have been developing for externalising
interactions into explicit, first-class entities that can be
dynamically superposed, "just-in-time", over system components to
coordinate their joint behaviour.
-
2002/50 Antonia Lopes and Jose Luiz Fiadeiro.
-
Superposition: Composition vs Refinement of
Non-deterministic, Action-Based Systems
We show that the traditional notion of superposition as used for
supporting parallel program design can subsume both composition and
refinement relationships when non-deterministic behaviour of action-based
systems is considered. For that purpose, we rely on a categorical
formalisation of program design in the language CommUnity that we are also
using for addressing architectural concerns, an area in which the
distinction between composition and refinement is particularly important.
-
2002/51 Luis Filipe Andrade and Jose Luiz Fiadeiro.
-
Service-Oriented Business and System Specification : Beyond
Object-Orientation
Based on the identification of some shortcomings of object-oriented
methodology and technology to address the challenges of supporting
the engineering and deployment of Web Services, we suggest that
alternative approaches can be found in what we call "coordination
methodologies and technologies" - a set of modelling primitives,
design principles, design patterns, and analysis techniques that we
have been developing for supporting the construction and evolution of
complex software systems that need to operate in very volatile and
dynamic environments.
![[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}
