An interesting computational challenge is posed by finding the diagram in diagramless crossword puzzles. We describe two approaches to placing the words in the diagram to form a crossword puzzle, given the "across" and the "down" words. One algorithm systematically tries the possibilities. By discarding partially completed puzzles the solutions for large puzzles can be found in a reasonable amount of time. The second algorithm uses on intelligent search strategy building up the diagram word-by-word. Both methods were programmed in Modula-3, a strongly-typed, object-oriented language. We describe the programs and analyze their performance on a SPARC computer.>

The VERT (verification of real-time programs) project is surveyed. The goal of the project is to assist the development of correct real-time programs. VERT is based on modeling concurrent programs with colored Petri nets. The investigations of the net model of the program reveal static and dynamic properties of the original program. In particular critical path analysis of the nets is used to determine if the program meets the timing constraints. Several aspects of the VERT project are addressed: translation of concurrent programs into colored Petri net models, algorithms for analysis, and visualization of net models.>

We give an algorithm for type inference in a language with functions, records, and variant records. A similar language was studied by Cardelli who gave a type checking algorithm. This language is interesting because it captures aspects of object-oriented programming using subtype polymorphism. We give a type system for deriving types of expressions in the language and prove the type inference algorithm is sound, i.e., it returns a type derivable from the proof system. We also prove that the type the algorithm finds is a “principal” type, i.e., one which characterizes all others. The approach taken here is due to Milner for universal polymorphism. The result is a synthesis of subtype polymorphism and universal polymorphism.