Search

An essential part of a significant scientific investigation is communication of the findings to others interested in the particular field. Hence, preparation of at least some of your laboratory reports in the form of a scientific paper is regarded as an important part of your experience in this course.

The research reported in this paper is concerned with the testing of software which is being developed in a structured way. The advantages which accrue from a well structured or modular organisation of software depend upon an ability to independently test a module well before the full development of all the modules with which it communicates. This paper describes a technique (finite state testing) which effectively organises data objects into equivalence classes and exercises a module using a representative of each class. As a technique it has an affinity with both the type checking performed by a conventional compiler and the assertion checking performed by a so-called verifying compiler. It is however a practical technique which has been used in experimental systems and is being incorporated in a prototype program development system.

This paper presents a definition in VDL (the Vienna Definition Language) of a simple message processing system using a polling algorithm. It illustrates an application of VDL in a new area and by defining extensions and changes to the original system demonstrates the flexibility of VDL as a formal definition tool.

The syntactic inference problem consists of deciding, for a given set of words, whether there exists a grammar such that its language includes these given words; and also of actually finding any such grammars. In this paper, the problem is considered for DOL-systems. The stress is on the second, constructive, part of the problem. The initial information may have various forms. Most of the results deal with cases in which

Given an n × n grid of n2 points we must select as many as possible so that no three are in a straight line. This paper reviews results concerning the problem and provides a few minor proofs, additions and generalisations.

Three new types of context sensitive parallel rewriting systems, called global context L-systems, rule context L-systems and predictive context L-systems are introduced in this paper. We investigate the generative power of these new types of context sensitive parallel rewriting systems and we compare it to the generative power of TOL-systems [81], L-systems with interaction [92], regular grammars and context sensitive grammars.

The overall performance of a process computer system depends on how well the computer resources are dynamically allocated to the various control tasks. It is often possible to greatly improve the performance once the resource allocation is known. This paper presents a software approach for obtaining this information. It concentrates on measuring the two most important resources: the hardware processor and the memory storage. As an example of the benefits that can be obtained, the measurement of a GEPAC 4000 computer used for nuclear power plant control will be discussed. However the techniques and ideas can be used to measure any process computer system. For the system measured, it is shown that there exists unnecessary movement of programs to and from secondary memory. The cause and correction of the problem is given. Measurements of the modified system show that a factor of two improvement in the through-put was obtained. A corresponding drop in secondary storage transfers is shown.

Young children should have maximum access to interactive computation so that they can use the machine as a tool for mathematical thinking of the most general kind. And, if children are given an understanding of the theoretical capabilities of machine computation, they might use it for more effective study of their own thinking about the world. With these as goals, we produced an experimental course for teaching computer programming concepts to children who had no previous experience with a computer. This paper discusses the results of that experiment and what they suggest about how children react to different programming languages and problems, and programmable devices. We provide details of the curricula and remarks on the students' experiences.

The Reidemeister-Schreier method yields a presentation for a subgroup H of a group G when H is of finite index in G and G is finitely presented. This paper describes the implementation and application of a FORTRAN program which follows this method. The program has been used satisfactorily for subgroups of index up to several hundred.

The SCT is as far as we can go without introducing serious machine dependencies. The remaining steps in the process fall beyond the scope of this paper.

Part II of this paper deals with treatments of statical errors as mentioned in the introduction of Part I. In recent years several attempts have been made to construct parsers for detecting or correcting syntactical errors automatically [3, 6, 7, 9 ]. We introduce an error correcting algorithm for a part of the ALGOL-60-BNF-Syntax based on techniques for treating regular languages which were developed earlier [3]. Three types of errors are investigated: deletion-(G), mutation-(H) and insertion-(J)-errors. The technique will be demonstrated by choosing two nontrivial examples of the BNF part of the ALGOL-60-syntax, namely the unsigned numbers as a regular event and the arithmetic expressions as a nonregular one.

This paper is devoted to the presentation of a two-parameter family M k t of parsers for general context-free grammars; the algorithms have a top-down structure, in which all the possible candidate parses are investigated in parallel. Backtracking is avoided by keeping track of the stage reached in all parses in a set of “states”. The integer parameters t and k describe tests performed on strings of terminals, of length t and k respectively, to the right of the point currently reached in the analysis of an input string. The tests involving parameter k enhance the performance of the parser on grammars with LR(k) characteristics, whereas those involving parameter t are most suited for grammars showing LL(t)-type conditions. However, the use of parallelism enables the algorithm to work on any CF-grammar.

In 1971 we presented a programming language, EUTERPE, as a tool for modeling musical structures ([Smoliar, 1971]). We demonstrated that this language provided a formalism wherein familiar concepts of musical analysis could be readily expressed. We also discovered that the language could be used to produce intriguing specimens of original composition ([Smoliar, 1972]). In this paper we wish to consider extending the analytical and compositional potential of EUTERPE.

The main body of this paper is devoted to suggestions on mechanical mathematics (sections 3 and 4) and an analysis of the relations between mathematics and physically executable procedures (section 5). The more general comments in the first two sections are to round off the picture.

In the fall of 1969 Carnegie-Mellon University acquired a PDP-10 to support the research of the Computer Science Department. This research involves the production of a substantial number of large systems programs of the type which have typically been written in assembly language, e.g., compilers, interpreters, etc. In many cases it was resolved to use a higher-level language to implement these systems. This decision immediately lead to another question: which language. In turn this lead to a consideration of the characteristics, if any, which are unique to, or at least exaggerated in, the production and maintenance of systems programs. One product of these deliberations was a new language which we call Bliss. In this paper we shall deal with the design considerations which most influenced the nature of Bliss and how these considerations manifest themselves in the language.

In this paper, we describe a new kind of software monitor for the performance analysis of CP67/CMS,-a time sharing system running on the IBM 360/67, and a method for designing representative workloads to simulate time-sharing loads.

In a precedent paper (Aguzzi 1973) we defined a formal system (APS) designed, essentially, in order to formally define, in an interpretative way, syntax and semantics of programming languages.

The following ideas have come up in connection with a research project APL-440 which is still in operation. The aim of the research group (at present the author of this paper and his co-worker N. Wilsing) is to study practical and theoretical aspects of dialog languages by means of a special model. Language and system APL-440 are made up of both a dialect of K. E. Iverson’s language APL (Iverson[2]) and an implementation on a TR440/TR86-System at the Rechenzentrum of the Hamburg University. An implementation of APL already existing is APL\360. There is no common opinion about what dialog languages should be (see Klerer, Reinfelds[3] and Sammet[4]). On the other hand it is necessary for a task like the above-mentioned project to select some possibilities from many others for a first verification.

This paper is concerned with a subject that is generally neglected - computers that cannot be reporgrammed. The title calls attention to an assumption that everybody makes and so no one is conscious of making: If you want a computer to do something, you must have a program prepared for the purpose. To be explicit, someone must conceive an effectively complete procedure for the job, specify it accurately in terms that the computer can accept, and command the computer to carry out the procedure as specified.

This paper presents a formal tool for the description of the design logic of programming language translators.