Fast algorithms for the elimination of common subexpressions
We give two algorithms for computing the set of available expressions at entrance to the nodes of a flow graph. The first takes O(mn) isteps on a program flow graph (one in which no node has more than two successors), where n is the number of nodes and ...
Developmental systems with locally catenative formulas
A locally catenative sequence of strings of letters is such that each string in the sequence, after an initial stretch, is formed by concatenating strings which occurred at some specified distances previously in the sequence. These kinds of structures ...
A note on multihead automata and context-sensitive languages
In this note we show that the following two statements are equivalent: (1) Any language over a one-letter alphabet, which is accepted by some nondeterministic multihead automaton can also be accepted by some deterministic multihead automaton. (2) ...
Zur theorie der partiell-linearen Realisierungen endlicher Automaten
This paper presents an approach to the partial-linear realization of finite automata which is independent of the numerous publications on linear automata. Among other results this theory allows to describe more concisely the theory of families of shift-...