mail toRob Kremer

List of Possible Thesis Topics

for graduate study with Rob Kremer

Note This page is a list of suggested M.Sc. topics that I would be interested in supervising (not that I wouldn't take other suggestions too).  Some of them are not yet documented, but I have listed them anyway -- if they sound interesting, let me know and we can discuss them. 
Rob Kremer

Table of Contents
Software Engineering-Related Topics Concept Map and Agent-based Systems-Related Topics

Software Engineering-Related Topics

Object Oriented Design Notation Implementation using Constraint Graphs
Constraint Graphs can be used to describe and implement various other graphical (concept mapping) formalisms. It could be used to implement and extend the various object oriented design notations such as OMT notation, Booch notation, etc. The figure below shows a first-cut implementation of OMT where the arcs are all type-constrained such that the designer-user is prevented from making several kinds of errors.
An example OMT notation diagram using the Constraint Graphs concept mapping language tool
References Kremer, R. & Flores-Mendez, R. (1997). KSI Software., Knowledge Science Institute, University of Calgary, Canada. 

Coad, P., North, D. & Mayfield, M. (1995). Object Models: Strategies, Patterns, and Applications, Yourdon Press. 

Booch, G. (1994). Object Oriented Design With Applications, Benjamin/Cummings. 

Cox, B. J. (1991). Object-Oriented Programming: An Evolutionary Approach. Reading, Mass, Addison -Wesely. 

Rumbaugh, J., Blaha, M., Premerlani, W., Eddy, F. & Lorensen, W. (1991). Object-Oriented Modeling and Design. Englewood Cliffs, N.J., Prentice-Hall. 

Using Concept Maps and Web Hypertext for Project Organization and Control
Concept maps can be used as a 2½-d guide to hypertext (Web) information. Some of the KSI concept mapping software can be configured to navigate the Web when the user clicks on the concept map's nodes. With the a good tool infrastructure and discipline this ability might be used as means for groups of software engineers to design and manage the software engineering process on the Web. (See the figure below for an example.)
A concept map-based application for manage the software engineering process
References Kremer, R. & Flores-Mendez, R. (1997). KSI Software., Knowledge Science Institute, University of Calgary, Canada, 

A Reusable Class and Template Library of Patterns
Programming patterns are a useful way for software designers to discuss designs. But many patterns map nicely into classes or templates that might be placed in a class (or template) library for more concrete use. Some examples already exist in the KSI general-purpose library (see the Command and Observer modules).
References Gamma, E., Helm, R., Johnson, R. & Vlissides, J. (1995). Design Patterns: Elements of Reusable Object-Oriented Software. Reading Mass., Addison Wesley. 

Pree, W. (1995). Design Patterns for Object-Oriented Software Development. Reading Mass, Addison-Wesley. 

Buschmann, F., Meunier, R., Rohnert, H., Sommerlad, P. & Stal, M. (1996). A System of Patterns: Pattern-Oriented Software Architecture. West Sussex, England, John Wiley & Sons. 

Coplien, J. O. & Schmidt, C. C., Eds. (1995). Pattern Languages of Program Design. Reading, Massachusetts, Addison-Wesley.

A Visual Front-end for WebMetrics
WebMetrics is an automatic software engineering metrics gathering and analysis tool being researched by Guancarlo Succi.  This project is would provide a Constraint Graphs concept mapping interface part of WebMetrics. 

A Visual Front-end for CoMo-Kit
CoMo-Kit is a software engineering tool that deals with the modeling and the management of complex work processes being developed at the University of Kaiserslautern and locally by Frank Maurer.  This project is would provide a Constraint Graphs concept mapping interface part of CoMo-Kit.

Adding a "Make" tool to a Constraint Graphs Version Specialized to Object Model Notations
Given that a Constraint Graphs tool exists for object oriented design (see the section on "Object Oriented Design Notation Implementation using Constraint Graphs"), one could use hypermedia techniques to annotate the concept map model with references to the actual source code modules.  With the addition of a few constructs (node and arc types) to the notation, one could actually have Constraint Graphs perform a "make" of a project to call compilers and linkers to build the executable code.  In essence, this project would build a truly visual, general purpose programming environment.

Concept Mapping-Related Topics

Design and Implementation of a Service Descriptor Language
In CASA (Collaborative Agent System Architecture), service agents may advertise services they are capable of preforming to Yellow Pages agents.  Subsequently, other agents my search for such services in using the Yellow Pages agents.  We need a general-purpose language that will serve to describe these services along with an ontology of services.  Amoung the attributes of a service descriptor are:
  • A machine-readable service descriptor
  • A short text human readable descriptor
  • A long text (help style) human readable descriptor
  • A generic hierarchical structure appropriate for interface agents to add this service to a menu path in their interface
  • Object associations for this service
  • Preconditions for application of this service
  • A machine-readable description of how to call this service
  • Any parameters

Practical Layout Algorithms for Concept Maps
There are several graphical concept mapping tools built at KSI, both in C++ and in Java, but all of them currently rely on users laying out the concept maps.  Many applications of of concept maps start with a computer-generated, "conceptual" concept map which specifies the nodes and the arcs between the nodes; but there is no (or very little) layout information.  Algorithms and heuristics must be devised to perform this layout so that these concept maps may be reasonably be presented to the user (who may choose to alter the layout, but wants a good start).  In addition, good user interfaces that allow the user to intuitively specify the parameters for the layout algorithms are required.  Example layout algorithms include simulated annealing, top-down or left-right tree layout over a set of arc types, shortest arcs, minimized crossed arcs, and cluster analysis.

The Role of Context in Constraint Graphs
In some situations, simple node-and-arc concept maps must be extended to include contexts in order to express complex ideas (see the figure below).  Contexts serve to partition the graph such that one may refer to an entire subset (as the terminal of an arc). 

Unfortunately, the literature contains no consciences on the semantics of contexts, so the a detailed and generalized semantics must be be worked out for Constraint Graphs.  In addition, the syntactical user interface for contexts must be clearly defined; for example, when one drags a node to overlap a context, is is placed into the context or is just overlapping?

A Conceptual Graph that describes the sentence "Tom believes Mary wants to marry a sailor."  Two nested contexts (a proposition and a situation) are required to express this idea.
References Kremer, R.  1997.  Constraint Graphs: A Concept Mapping "Meta-Language".  Ph.D. dissertation, Department of Computer Science, The University of Calgary, Calgary, Canada.

Sowa, J. F. 1984. Conceptual Structures: Information Processing in Mind and Machine. Reading, Massachusetts, Addison-Wesley.

Combining Constraint Graphs and a KRS Engine on the Web
KRS is a visual form of the CLASSIC term subsumption language used in artificial intelligence.  KRS was developed by Brian Gaines at KSI and runs on the Mac.  The Constraint Graphs definition of the KRS syntax is shown in the figure below.  Constraint Graphs can use this definition to implement an graphical KRS editor, but it cannot perform the inferences that KRS can.  The development web-based version of KRS that interfaces to Constraint Graphs would broaden the availability of KRS to a wide variety of platforms.  It would also be a significant and interesting software engineering undertaking.
The Constraint Graphs definition of the KRS language.
An example of KRS knowledge based written using the above Constraint Graphs definition.  If George where listed as only on instance of Person, then KRS could infer that George was an instance of Child based on this age.
References Gaines, B. R. 1991b. An Interactive Visual Language for Term Subsumption Languages. 
IJCAI-91. Sydney, Australia.

Kremer, R.  1997.  Constraint Graphs: A Concept Mapping "Meta-Language".  Ph.D. dissertation, Department of Computer Science, The University of Calgary, Calgary, Canada.

Creating Light Weight (GIF) Concept Maps for WWW Hypertext Navigation
KSI has several concept map creation tools and some that work on the Web.  These seem useful for "mapping" the Web hypertext in a intuitive and visual way.  But the overhead of downloading a helper program, a plugin or even a Java applet seems overly cumbersome for many applications.  A translator from the KSI concept mapping formats to clickable (mapped) GIFs be an interesting project; particularly if combined with a study of its use.

Multi-user Web Server for Concept Maps

Group awareness tools for Multi-user Web Concept Maps

Concept Map-based Web Navigation Tools

A Scripting Language for Fully Programmable Concept Maps

A Visual Interface for the CGKEE Server

A Full Constraint Graphs "native" Implementation of the Conceptual Graphs Canon

Putting an OODB/CORBA Backend on Constraint Graphs

Constraint Graphs Interfaces for Various Concept Mapping Languages

A Pure-Java Version of Constraint Graphs

The University of Calgary
Up to page above
up to Rob Kremer's home page

Software Engineering Research Network
mail toRob Kremer
Last Modified Oct. 29, 1997
List of Possible Thesis Topics
for graduate study with Rob Kremer