Project Proposals 2003-2004

 

Igor Potapov

igor@csc.liv.ac.uk

 

Here are a number of projects I am willing to supervise.

 

I will be available to discuss the projects listed here and to consider Student Specified projects by appointment. 

 

I am interested in modelling and theoretical analysis of discrete event systems, communication protocols and sequential/parallel algorithms. Along these lines, I am offering the following projects.

 

CODE

TITLE

DESCRIPTION

IP1R

Experiments with data compression

At the beginning of the project you will get the description of the compression method. The idea is based on a beautiful way for representing all nonnegative rational numbers by unique binary sequences. The aim of the project is to design the compression/decompression algorithm, to implement it in C, C++ or JAVA and to analyse the efficiency and applicability of the new compression method. This project contains a number of challenging problems in data structures and algorithm design, but perfectly within the scope of a third year student.

IP2R

Reachability problems in Iterative Maps

Most of real dynamical systems, such as the model systems in physics, chemistry, biology, ecology, economics etc, are described by difference equations, where the system evolves through a set of discrete time steps. The simplest models of difference equations are the iterative maps because the future value of some variable at time n+1 depends only on its value at the present time n (here n is an integer). An iterative map is of the form x_(n+1) = f(x_n) where f(x) is called the mapping function. The significant property of iterative maps and real dynamical systems is that the slightest uncertainty about initial state leads to very big uncertainty after some time. With such initial uncertainties, the system▓s behaviour can only be predicted accurately for a short amount of time into the future. So many fundamental interesting questions about iterative maps are about reachability: Starting from a state in set S, can we reach a state in set S'? The question of whether these problems have an algorithmic solution or have not is important since it gives the answers on many practical questions related to the verification of software products and analysis of model systems, whose components are governed by simple laws, but whose overall behaviour is highly complex.

The aims of this project are to analyse several known cases where it is possible to predict the dynamics in iterative maps and to develop similar methods for different dynamical systems.

IP3P

ASM-based modelling of Membrane Computing

Computing with membranes (P systems) is a branch of Molecular Computing initiated by Gh. Paun. A P system is a computing model, which abstracts from the way the alive cells process chemical compounds in their compartmental structure. In short, in the regions defined by a membrane structure we have objects, which evolve according to given rules. The objects can be described by symbols or by strings of symbols. By using the rules in a nondeterministic, maximally parallel manner, one gets transitions between the system configurations. A sequence of transitions is a computation. With a halting computation we can associate a result, in the form of the objects present in a given membrane in the halting configuration, or expelled from the system during the computation. Various ways of controlling the transfer of objects from a region to another one and of applying the rules, as well as possibilities to dissolve, divide or create membranes were considered. http://psystems.disco.unimib.it.

The aims of this project are to design a formal framework for modelling the membrane computation in Abstract State Machine (ASM) model and to write formal specifications in ASML for several variants of P systems.

IP4P

Algorithmic Music Composer

The goal of this project is to produce some code that composes music according to well-founded composition rules and guidelines. Many mathematical and computer science disciplines has been applied in musicology, i.e. set theory, fractals, cellular automata, iterative maps etc. The idea is that the outputs of certain mathematical operations give a sequence of numbers. If we assign certain tones to elements of these number sequences we obtain the corresponding tone sequences. There are several example of automatic music composition such as Fractal composition, Music generated by iterative maps, Mozart Dice Game or Joplin Melody Dicer. The potential student should have good programming experience and basic music background.

IP5P

Modelling of the mobile automata

A class of automata similar to cellular automata but which have a single active cell instead of updating all cells in parallel. In a mobile automaton, the evolution rules apply only to the active cell, and also specify how the active cell moves from one generation to the next. All cells that are not active remain the same from one generation to the next. Mobile automata can therefore be considered a hybrid between elementary cellular automata and Turing machines.

The aim of this project is to develop the system for design and animation of the mobile automaton (for more details see here http://mathworld.wolfram.com/MobileAutomaton.html).

IP6P

Implementation of the algorithm for Domino Snake problem

Wang tiles (or Wang dominoes), first proposed by Hao Wang in 1961, are equal-sized squares with a color on each edge http://en.wikipedia.org/wiki/Wang_tile. The standard question is whether a given finite set can tile the plane. This means that copies of the tiles can be arranged to fill an infinite plane, such that contiguous edges always have the same color. The tiles cannot be rotated or reflected. The snake tiling problem takes as input a finite set of Wang tiles (square tiles with coloured edges) and asks whether it is possible to form a snake using copies of these tiles to connect to points of the plane, where consecutive tiles of the snake must match in colour in their adjacent edges. The aim of the project is to implement the program with graphical interface for solving the snake problem on the plane.

IP7D

Practical Class Allocation System

Practical class allocation for this department is currently performed with the minimum of computer assistance. In particular, there is no system, which helps to create the practical class allocation according to the student’s choice, current timetable and capacity of the labs. At the moment everything must be created entirely by hand.

The aim of the project is to design and implement web-oriented automatic practical class allocation system. This project has three main objectives:

  1. to design a database for practical allocation system;
  2. to create a web-oriented user interface suited to use in this department, able to generate the necessary problem description files and transform the resulting allocation table into the sets of tables published to students and staff;
  3. to design an algorithm for generating practical class allocation.

IP8D

Visualisation of the Minority Game

Minority game is a variant of the famous El-Farol's bar problem: when is it sensible to go to the pub? In this model, 100 people would like to go to a bar (El Farol) which is too crowded if there are more than 60 people. The minority game is a repeated game where N (odd) players have to choose one out of two alternatives (say A and B) at each time step. Those who happen to be in the minority win. Although being rather simple at first glance this game is subtle in the sense that if all players analyse the situation in the same way, they all will choose the same alternative and will lose. Moreover, there is a frustration since not all the players can win at the same time.

The aim of this project is to implement an animation of the Minority Game where players have simple learning mechanisms.

 

 

Other Research projects

 

(IP3R3) Modelling and Analysis of Self-Modifying Communicating Processes

 

Self-Modifying Communicating Process is similar to an ordinary communicating process, except that each transition not only changes the state and read or send message, it also modifies the set of transitions of the process.  Self-Modifying Communicating Process is a formal framework of open protocols, which can connect different devices in a different way. Unfortunately it is extremely difficult to analyse and design it without a formal theory. You have a chance to start this research project and to get knowledge and experience in a new field.     

 

References:

·       Several experiments in elementary self-modifying protocol games, such as Nomic

http://www.cs.uu.nl/~gv/abstracts/exp-nomi.html

·       Self-Modifying Finite Automata

http://cs.wpi.edu/~jshutt/smfa.html