Determining the relative execution frequency of program regions is essential for many important optimization techniques, including register allocation, function inlining, and instruction scheduling. Estimates derived from profiling with sample inputs are generally regarded as the most accurate source of this information; static (compile-time) estimates are considered to be distinctly inferior. If static estimates were shown to be competitive, however, their convenience would outweigh minor gains from profiling, and they would provide a sound basis for optimization when profiling is impossible.

Abstract Index preparation is a tedious and time‐consuming task. This paper indicates how the indexing process can be automated in a way that is largely independent of a specific typesetting system and independent of the format being used. Fundamental issues related to this process are identified and analysed. Specifically, we develop a framework for placing index commands in the document. In addition, the design of a general‐purpose index processor that transforms a raw index into an alphabetized version is described. The resulting system has proved very useful and effective in producing indexes for several books, technical reports and manuals. A comparison of our system with indexing facilities available from a variety of other document preparation environments is given.

We present a linear time algorithm for eliminating null rules in context free grammars. Until recently all algorithms given in the literature for this problem required exponential time.

A new algorithm for recognizing and parsing arbitrary context-free languages is presented, and several new results are given on the computational complexity of these problems. The new algorithm is of both practical and theoretical interest. It is conceptually simple and allows a variety of efficient implementations, which are worked out in detail. Two versions are given which run in faster than cubic time. Surprisingly close connections between the Cocke-Kasami-Younger and Earley algorithms are established which reveal that the two algorithms are “almost” identical.

A new on-line context free language recognition algorithm is presented which is derived from Earley's algorithm and has several advantages over the original. First, the new algorithm not only is conceptually simpler than Earley's, but also allows significant speed improvements. Second, our algorithm serves to explain the connections between Earley's algorithm and the Cocke-Kasami-Younger algorithm. Third, our algorithm allows an implementation which uses only 0(n2/log n) operations on bit vectors of length n, or 0(n3/log n) operations on a RAM. This makes it the fastest known on-line context free language recognition algorithm.

A model of protection mechanisms in computing systems is presented and its appropriateness is demonstrated. The “safety” problem for protection systems under our model is to determine in a given situation whether a subject can acquire a particular right to an object. In restricted cases, one can show that this problem is decidable, i.e., there is an algorithm to determine whether a system in a particular configuration is safe. In general, and under surprisingly weak assumptions, one cannot decide if a situation is safe. Various implications of this fact are discussed.

A parsing method for strict deterministic grammars is presented and a technique for using it to parse any deterministic language is indicated. An important characterization of the trees of strict deterministic grammars is established. This is used to prove iteration theorems for (strict) deterministic languages, and hence proving that certain sets are not in these families becomes comparatively straightforward. It is shown that every strict deterministic grammar is LR(0) and that any strict deterministic grammar is equivalent to a bounded right context (1, 0) grammar. Thus rigorous proofs that the families of deterministic, LR ( k ), and bounded right context languages are coextensive are presented for the first time.

Recently strict deterministic grammars and languages have been introduced [9,10,11]. This family of languages is quite fundamental in the study of the mathematical properties of deterministic languages and in dealing with some classical families of grammars such as LR(k) and bounded right context grammars [7,8,14]. These grammars are closely related to LR(0) grammars [1,12,13,14], in fact each strict deterministic grammar is also LR(0). In the present paper, we consider the question of how to parse strict deterministic grammars. We introduce part of a more general theory called "characteristic LR(k) parsing". This actually produces parsers which are tuned to the characteristics of a particular family of grammars. We apply the theory to the family of strict deterministic grammars and we get parsers which are as fast as canonical LR(k) parsers but are substantially smaller. They are not necessarily minimal but we postpone any discussion of minimality to the sequel.The techniques used in the present discussion are quite general [5]. For instance, the study in [3] is similar in spirit to our technique. The optimization techniques for LR(k) parsers in [2] do not work in the case k = 0 without modification. After modifying those methods for k = 0, it can be shown that our parsers cannot be produced by those techniques. This fact has its positive aspect in that our parsers may be smaller and its negative aspect in that error detection may be delayed.The present paper is divided into the present introduction and three sections. In the remainder of this introduction, some basic definitions of strict deterministic and LR(k) parsing are given. We have tried to follow [1] as much as possible in order to minimize the amount of new material to be absorbed. The order of the results is the order needed to prove that the characteristic parser works. In Section III, we apply the theory of Section II to strict deterministic parsing. A simple example shows that the new parsers can be unboundedly smaller than the canonical LR(0) parser.The present paper is meant to be an extended abstract and no proofs are included.The rest of the introduction is concerned with notational conventions for the technical concepts needed.

A general theory of canonical precedence analysis is defined and studied. The familiar types of precedence analysis such as operator precedence or simple precedence occur as special cases of this theory. Among the theoretical results obtained are a characterization of the structure of precedence relations and the relation of canonical precedence schemes to operator sets.

Cellular switching theory gives rise to the problems of counting the number of equivalence classes of m X n matrices of zeros and ones under: 1) row and column permutations; and 2) row and column permutations together with column complementations. A number of techniques are given for the solution of these problems.

A formal definition of one grammar "covering" another grammar is presented.It is argued that this definition has the property that G' covers G when and only when the ability to parse G' suffices for parsing G.It is shown that every grammar may be covered by a grammar in canonical two form.Every A-free grammar is covered by an operator normal form grammar while there exist grammars which cannot be covered by any grammar in Greibach form.Any grammar may be covered by an invertible grammar.Each A-free and chain reduced LR(k) (bounded right context) grammar is covered by a precedence detectable, LR(k) (bounded right context) reducible grammar.

The family of strict deterministic languages has been studied for its theoretical properties and applications to parsing. In particular, these languages have been shown to be precisely the prefix-free deterministic languages. Deterministic pushdown automata are called (quasi-)real time if they have no (only a bounded number of consecutive) null moves. It is shown that for strict deterministic languages, the quasi-real-time and real-time constraints are equivalent (except for $\{ \Lambda \} $). A grammatical characterization of these languages is also given. For quasi-real-time strict deterministic languages, an easy and elegant decision method is given for testing regularity. For all known methods of accepting deterministic languages, it is shown that the families of real-time languages are a proper subset of the full families. A relation is established among these sets, the simple deterministic languages, and some hierarchies.

A new family of grammars is introduced.A grammatical characterization of the one-way nondeterministic stack languages is obtained.Characterizations of the languages accepted by nonerasing stack automata and by checking automata are also derived.

This book consists of two parts, the first being a survey of the mathematical theory of Boolean functions. Chapter 1 introduces basic definitions, various normal forms, prime implicants, and symmetric functions. In an appendix to Chapter 1, an unpublished combinatorial and nontrivial theorem of Bakos is given. (This theorem yields a uniform construction of Gray codes as a consequence.) Chapter 2 gives the standard theory of minimality. Applications to special cases such as monotonic or symmetric functions are given. Chapter 3 discusses interrelationships between conjunctive and disjunctive normal forms. Chapter 4 deals with functional completeness and the Post–Yablonsky theorem is proven. Some applications to finite automata are given. Chapter 5 is concerned with the decomposition of truth functions. Chapter 6, on numerical problems, is particularly good. Groups are used to classify truth functions. A form of Polya's theorem is given and the work of Polya, Slepian, and the reviewer is presented. A number of special cases are worked out, including some of the results of Povarov. Chapter 7, on linearly separable functions, gives a number of characterizations.

A device is presented which has its memory organized as a linear list, a type of storage equivalent to having two pushdown stores. Attention is then focused on the nondeterministic automaton (called an lsa ) which results when the input is read one-way and the device operates in real-time. The set of words (called a language ) accepted by an lsa is extensively studied. In particular, several characterizations and closure properties of languages are given.

Using a new definition for the equivalent of state assignments, the number of nonequivalent state assignments is derived. The exact number of nondegenerate state assignments is also compted.

Compilation consists of two parts, recognition and translation. A mathematical model is presented which embodies salient features of many modern compiling techniques. The model, called the stack automaton, has the desirable feature of being deterministic in nature. This deterministic device is generalized to a nondeterministic device (nondeterministic stack automaton) and particular instances of this more general device are noted. Sets accepted by nondeterministic stack automata are recursive. Each set accepted by a deterministic linear bounded automaton is accepted by some nonerasing stack automaton. Each context-sensitive language is accepted by some (deterministic) stack automaton.

A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation, the latter. Several solvability questions are also considered.

Results in the literature on sequential machines prove that it is not possible to determine the minimal form of a machine by external measurements. By changing the concept of external measurement, an ``effective solution'' to this identification problem is given. The solution utilizes an important result in the theory of sequential relations.

Formulas and algorithms have recently been given for calculating the number of symmetry types of functions, networks and automata under various transformation groups. In almost all cases, the computations involved are quite difficult and require the use of a digital computer. In this paper, asymptotic estimates are given for these numbers, which are trivial to compute and which are very accurate in most cases even for small values of the parameters.

Abslract.In a recent paper, C. S. Lorens [4] has focused attention on invertible Boolean fu~etions.Lorens has counted the number of classes of such functions by considering the same group acting o~ both the domain ~md range of such functions.In this work, a simplified algorithm for obtaining Lorens' results is given which extends his work by Mlowing differenb groups or~ the domain and range.

Symmetric and partially symmetric functions are studied from an algebraic point of view. Tests are given for detecting these properties. A more general approach involving the concept of ?-symmetric functions is given. A canonical form is derived for ?-symmetric functions which leads to synthesis procedures that improve results of Shannon.