Research Forum 2003

The 25-th anniversary of the Department of Computer Science, Memorial University of Newfoundland, was an occasion for a variety of "special events". Research Forum 2003, organized on November 14, 2003, was one of these events; its main objective was to present to faculty and administrators, to our students, and to the community at large, some of the research activities in our department.

The record of the Research Forum 2003 sometimes goes beyond the presentations in an attempt to show a broader context for selected long-term research initiatives. It is believed that such a broad perspective can provide an interesting enhancement of presentations which typically concentrate on only a few aspects of research.

The contributions demonstrate a wide spectrum of research interests in the Department.

Dr. Wolfgang Banzhaf overviewed his work (with Andre Leier) on the application of genetic programming to the design of quantum algorithms. The difficulties and perspectives of such an approach were discussed using Hogg's quantum algorithm and the Deutsch-Josza problem as case studies.

Dr. Miklos Bartha discussed algorithms for the elimination of redexes in deterministic elementary soliton graphs. In particular, he proved that an elementary soliton graph is deterministic if and only if it can be reduced to a graph which does not contain even-length cycles. Soliton graphs are studied in the context of modern microelectronics and molecular computing.

Dr. Ashoke Deb described how a dataflow graph language (Avon) can be used as an architecture description language. Avon describes programs as dataflow graphs, where the flow is "regulated" by predicates. It appears that the behavior of computer architecture can be described in a similar way.

Dr. Tony Middleton used non-procedural grammars, a concept similar to non-procedural programs, to increase transparency and "understandability" of formal definitions. A series of examples was provided to illustrate the differences between procedural and non-procedural definitions.

Dr. Jeffrey Parsons briefly described his work in the area of information modeling, that is, the process of identifying and representing information requirements during the early stages of information system development. The long-term objectives of this research include improved understanding of existing methods and tools for systems analysis and database design and management.

Dr. Jian Tang discussed outlier detection, an important branch of data mining concerned with discovering an exceptional behavior of objects. In particular, he proposed a measure which can be used to compare the capabilities of different outlier detection schemes.

Dr. Krishnamurthy Vidyasankar reviewed his long-term research in concurrency aspects of databases and distributed computing, with contributions in serializability theory, concurrency control methods, multidatabase systems, resiliency control, mutual exclusion algorithms, and many others.

Dr. CaoAn Wang presented recent developments in maximum weight triangulation of a point set in a plane. An upper bound for such triangulation of any planar point set was derived, and it was shown that if the point set forms a semi-circled convex polygon, the maximum weight triangulation can be found in O(n^2) time, where n is the number of points in the set.

Dr. Todd Wareham surveyed practical algorithms for common string problems; problems that find applications in many areas, from coding theory to computational molecular biology. Many variants of common string problems are known to be NP-complete and thus not solvable in general by polynomial-time algorithms. Recent results, however, suggest that there are useful cases that can be solved efficiently in practice.

Finally, Dr. Wlodek M. Zuberek illustrated his long-term research on applications of Petri nets and timed Petri nets to modeling and analysis of (complex) concurrent systems by discussing performance equivalence of models in simulation-based evaluation of multiprocessor systems.

The contributions were presented in four sessions of the Forum.

Printed copies of the record of Research Forum 2003 are available from the Department of Computer Science while quantities last. Electronic (pdf) versions of contributions are available for downloading (subject to Copyright by the Department of Computer Science):

Copyright 2004 by Department of Computer Science, Memorial University of Newfoundland.