As interactive computing has developed, a more comprehensive design methodology is required to produce high-performance software. To achieve this goal, consideration of user performance must be included as an integrated part of the development process. An approach that allows a software engineer to integrate user performance as a design dimension in interactive software system design is presented. This approach is used to study the design of a text editor.>

Inference of high-dimensional grammars is discussed. Specifically, techniques for inferring tree grammars are briefly presented. The problem of inferring a stochastic grammar to model the behavior of an information source is also introduced and techniques for carrying out the inference process are presented for a class of stochastic finite-state and context-free grammars. The possible practical application of these methods is illustrated by examples.

Inference of high-dimensional grammars is discussed. Specifically, techniques for inferring tree grammars are briefly presented. The problem of inferring a stochastic grammar to model the behavior of an information source is also introduced and techniques for carrying out the inference process are presented for a class of stochastic finite-state and context-free grammars. The possible practical application of these methods is illustrated by examples.

No abstract available.

The concept of abstract data types is extended to associate performance information with each abstract data type representation. The resulting performance abstract data type contains a functional part which describes the functional properties of the data type and a performance part which describes the performance characteristics of the data type. The performance part depends upon 1) the algorithms and data representation selected to represent the data type, 2) the particular machine on which the software realization of the data type is realized, and 3) the statistical properties of the actual data represented by the data objects involved in the data type. Methods for determining the necessary information to specify the performance part of the representation are discussed.

The authors would like to thank B. R. Gaines for his careful reading of both the paper1and the thesis [1]. Dr. Gaines is correct in pointing out that for application to the grammatical inference problem We have found, as Gaines has stated, that making this correction to the program does in fact yield more accurate models. We also concur with Dr. Gaines as to the two typographical errors pointed out in test grammar 1.

The performance of a hardware/software system is a function of both the deterministic properties of the computation being performed and the probabilistic properties of the information sequence being processed. This paper develops the idea of a computational cost which can be used to measure system performance and shows how this cost can be related to the structure of the system and the information processed by the system. Different ways in which this cost can be used to study system performance are presented.

An automated software design system emphasizing dynamic performance analysis is a goal of research currently being done at the University of Connecticut. An approach for providing low level operator performance information and implementation of the software is presented. This includes an operator definition process and incorporation of defined operators into data operation modules by association with a data structure. Along with a discussion of future plans, some advantages of the approach are mentioned.

The problem of the inference of finite-state probabilistic grammars is studied from two points of view. First, the theoretical aspects of grammatical inference are considered. Among the topics investigated are the structural and statistical properties of probabilistic grammars, methods for assigning probability measures to rewrite rules of probabilistic grammars, and statistical measures for determining how well an inferred probabilistic grammar approximates a sample set. The second concern of the study is the development and implementation of an algorithm for the inference of finite-state probabilistic grammars. This finite-state inference procedure produces a deterministic finite-state probabilistic grammar whose language approximates the sample set within a user-supplied acceptance region under the chi-square test. This procedure is enumerative. Heuristic tree-searching techniques are used to improve efficiency. The convergence of the procedure to an acceptable grammar is demonstrated and the steps of the procedure are theoretically justified. Test results of a PL/I implementation are presented. The inference procedure developed provides a means of synthesizing a probabilistic model of both physical and abstract systems from samples of their behavior.

An engineering-oriented performance model of a computation is developed by extending the concept of a computation structure to cover the performance costs appropriate to software modelling. The model allows both serial and parallel (multiprocessor) configurations,and the evaluation of both time space parameters for alternate realizations. A brief discussion on the use of the model as a mechanism to guide the performance optimisation of programs is included.

The problem of grammatical inference is introduced, and its potential engineering applications are demonstrated. Inference algorithms for finite-state and context-free grammars are presented. The application of some of the algorithms to the inference of pattern grammars in syntactic pattern recognition is illustrated by examples.

Inference of high-dimensional grammars is discussed. Specifically, techniques for inferring tree grammars are briefly presented. The problem of inferring a stochastic grammar to model the behavior of an information source is also introduced and techniques for carrying out the inference process are presented for a class of stochastic finite-state and context-free grammars. The possible practical application of these methods is illustrated by examples.

The problem of assigning a probability to each word of a language is considered. Two methods are discussed. One method assigns a probability to a word on the basis of particular measurable features of the language. The second method is applied to languages L(G) generated by a grammar G. A probability is associated with each production of G. These in turn define the word probabilities of each word in the language. The conditions for this assignment to be a probabilistic measure are derived.

Deterministic and probabilistic sequential machine theory is used to solve the estimation, prediction, and smoothing problem encountered in noisy discrete parameter systems such as digital data processors and information processing systems. Using Bayes' theorem, the equations describing the ideal estimator, predictor, and smoother are developed. These equations are used to define an infinite-state Mealy-type sequential machine that performs these calculations.

Abstract—Recent studies have shown that many noise processes in sequential networks can be described as a multinomial process, a Markov process, or a linearly dependent process. This paper extends the results of those studies to show how the statistics of any sequence selected from processes of this type can be calculated.