Proposals for Honour Year Projects

Frank Stephan's addresses are: (1) School of Computing, National University of Singpore 3 Science Drive 2, Singapore 117543 (2) Department of Mathematics, National University of Singapore 2 Science Drive 2, Singapore 117543 The office is in Building S14#06-06 and has telephone +65-6516-7354 The telefax in the main office of the School of Computing is +65-6779-4580 Office Hours: Tuesdays 15:00-17:00h (except 13.09.2005). The email address is fstephan@comp.nus.edu.sg

• Measure functions and randomenss tests (ps-file and pdf-file). From the viewpoint of recursion theory, a sequence is random whenever it is impossible to derive any useful information from known members about unknown members; this work deals with certain variants of the notion of randomeness and the relations between them. Slides of a talk on this subject can be found on the url of Jan Reimann.
  
  
• Indentifying Cliques with Queries
  A theoretic topic in fault diagnosis is the following: there are n processors and each can be working or faulty. The working processors can test the others and tell which of them is working or not. The faulty processors also might take the request to test other processors, but they might return any arbitrary information. The task is to determine by queries (i,j) which processors are working and which not, so query (i,j) to processor is asks whether i thinks that j is "in order" ("1") or "faulty" ("0"). This task is solvable as long as the majority of processors works properly. In the case that only a smaller quantity of processors is in order, say a third of all, the user is no longer able to determine the workking ones.
  Instead the user can determine up to three sets A,B,C of processors such that
  • Each processor in the set A says that the others in A are in order and those in B,C faulty;
  • Each processor in the set B says that the others in B are in order and those in A,C faulty;
  • Each processor in the set C says that the others in C are in order and those in A,B faulty.
  The user cannot find out which of these sets have the processors which are in order, but determining these sets A,B,C by queries is also a valuable goal. The project is based on the following paper:
  • William Gasarch and Frank Stephan. Finding isolated cliques by queries - an approach to fault diagnosis with many faults. This paper appeared as a report of Dagstuhl Seminar Proceedings 04421, Algebraic Methods in Computational Complexity , Internationales Begegnungs- und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany, 2005.
  The project's goal is to make an implementation on a webpage of the algorithms given there (in Java Script) and to write a theoretical summary. Additional improved algorithms are also welcome.
  
  
• Automatic Structures. Given a finite alphabet A, say A = {0,1,...,9}, one can define finite sequence on A like 003, 425, 324234, 812. A set X of such sequences is regular if a finite automaton is accepting its inputs, for example the set of all representations of numbers divisable by a fixed number c is a regular set. An automatic structure consists not only of X but also of relations and operations on X which can be recognized by finite automata. Goal of the project would be to investigate for certain given structures whether they can be represented in an automatic way. For example, this can be done for the group of integers, the group of dyadic numbers, the words over the alphabet {A,B,...,Z} with lexicographic ordering and certain well-ordered sets. Goal of the project would be to extend these investitagions to some natural structures which could come from set theory or other mathematical background and have not yet been considered in this field and to prove that these structures are automatic. Background material can be found in the papers awailable online: (1) On automatic partial orders; (2) Definability and regularity in automatic structures; (3) Automatic Structures: Richness and Limitations.
  
  
• Splittings of Learnable Classes. A topic investigated in complexity theory and recursion theory is whether certain sets can be split into two smaller one of the same or of incomparable degrees. Simmilarly one can investigate when an infinite learnable class can be split into two classes of the same complexity (with respect to intrinsic complexity defined by certain learnability reductions). Furthermore, one can investigate whether a class can be split into two classes of lower complexity. Under certain conditions these classes are incomparable with each other. The basis of this work would be a draft also containing the necessary definitions and some fundamental results. The student could either go for extensions of the results there in settings not considered by the authors or try to attack the still open problem whether there is a learnable class such that (1) this class has a splitting into two infinite classes and (2) any splitting of this class consists of two classes of the same intrinsic complexity.

• Coinductive Methods in formal language theory (ps-file and pdf-file). The purpose of this project is to reformulate (parts) of the classical theory of formula languages in terms of coinductive proof methods. As a motivation we consider the work by Antimirov who gave a coinductive proof method to decide language containment among regular expressions. This project is open to both mathematics and computer science students.
  
  
• Non U-Shaped Learning
  Inductive Inference is mathematical model for learning in the limit. There the learner reads more and more data of an unknown set and outputs hypothesis of programs generating this set such that from some time on every hypothesis is a program which generates the desired set. The learner itself might not remark directly that the hypothesis is already correct and therefore still update it from time to time.
  One recently studied question is the question when it is possible to learn in such a way that the learner never changes from a correct to an incorrect hypothesis. That is, there is no U-shaped learning behaviour of the form "incorrect - correct - incorrect".
  The project would be to give a review on the current knowledge on this field and to extend the the results for team learning as defined in this paper. It is not required to solve all open problems in this field but to attack some of them.
  It is possible to extend the studies and to write a master thesis about this topic. The problem studied in this extension depends on the performance of the student and the development of research in this field. A possible question would be to address the relation to behaviourally correct learning.
  A very recent paper on this topic is U-Shaped Learning may be necessary and it contains also all necessary formal definitions.