Division Members
Dr Paul Bell is mainly interested in computability and complexity theory and studying the decidability of problems related to algebraic structures, hybrid systems and formal languages. He has shown many problems to be undecidable in these areas mainly through reductions from modifications of existing undecidable problems such as the Post correspondence problem and Hilbert's tenth problem. For decidable problems, he is also interested in studying their computational complexity and thus tractability. He has written several papers in international conferences and journals of theoretical computer science on these topics.
He is also interested in scheduling problems and online algorithms related to multiprocessor systems. For such problems, the goal is to find an optimal dispatching of jobs to processors and optimal processor speeds that will minimise the total amount of energy used.
These are both currently very active areas of research with applications to many areas of Computer Science and Mathematics.
Dr Helmut Bez is interested in geometry and mathematical aspects of shape description for application in computer graphics and computer aided geometric modelling. He has a particular interest in rational parametrisation and is currently applying Lie group methods to the development of new theorems to provide a deeper understanding of Bezier curves and surfaces. Dr Bez is also interested in mathematical aspects of image processing.
Dr Walter Hussak is interested in non-classical logics and their applications to the specification of concurrency. His main research is into the decidability and expressiveness of fragments of first order temporal logics, and the application of both propositional and first-order temporal logics for specifying the infinite execution of cases of transactional concurrency. Much of the work in logic has close links with the classical decision problem of mathematical logic.
Most results have concerned the 'monodic' fragment of first-order temporal logic which is the main known decidable fragment. His main results have been to extend the classical part of the existing fundamental decidability result, to fragments which include both time-dependent and time-dependent function symbols, and the temporal part to fragments which include grammar operators and propositional quantification. The monodic fragment has been shown to be suitable for specifying schedules of concurrent transactions accessing unlimited data, in which the main correctness condition of serializability can be expressed in a first-order manner and is thus decidable. The significance of the work is in its contribution to the general aim of advancing the use of propositional temporal logic in computer science, which has received two ACM Turing awards, to first-order temporal logic.
Dr Daniel Reidenbach is mainly interested in two major subareas of theoretical computer science: algorithmic learning theory and formal languages. In particular, his research deals with patterns in strings of symbols, their underlying mathematical theory and the problem of computing such patterns. These topics show strong connections to various other fields in theoretical computer science and discrete mathematics, such as computability theory, combinatorics on words, and complexity theory.
Many of his recent results are related to so-called pattern languages, i.e., sets of strings that all follow a given pattern. His achievements include:
- deep insights into the algorithmic learnability of pattern languages, a prominent field of research in algorithmic learning theory,
- several results on the equivalence and inclusion problems for pattern languages, and
- establishing a novel field of research in combinatorics on words, studying the ambiguity of morphisms in free monoids.
Some of these results solved longstanding problems, and the corresponding publications won prestigious academic awards at international conferences in theoretical computer science.
Dr Ana Salagean is interested in sequences of random numbers for cryptographic applications. Random numbers are needed in numerous applications. Generating long sequences of random numbers by computer is more efficient than obtaining them from natural processes but, on the other hand, the numbers produced are not truly random (they are called pseudo-random). For cryptographic applications it is essential that the next "random" number cannot be deduced from the previous ones (for example, each number being the sum of the previous two would be a very bad choice). There are several ways of quantifying this unpredictability and we look at one particular type of measures called linear complexity and k-error linear complexity. While there are well known efficient methods for computing the linear complexity, there are currently no efficient algorithms for computing the k-error linear complexity, except for a few particular cases. Indeed, it is not known whether such algorithms exist at all or whether the problem is intrinsically difficult (NP-hard).
Her research aims to develop algorithms for computing the k-error linear complexity. Three approaches are considered: developing algorithms for more general classes of sequences, developing algorithms which give an approximate result but are much faster than obtaining the exact result, and deciding whether the problem is NP-hard. Two journal papers (in IEEE Transactions on Information Theory) and four conference papers have resulted from this work so far.
