The number of registers required for evaluating arithmetic expressions. (English) Zbl 0407.68057
MSC:
| 68Q99 | Theory of computing |
Keywords:
Combinatorial Analysis; Analysis of Algorithms; Register Allocation; Evaluation of Arithmetic Expressions; Strahler Number; Tchebycheff Polynomials; Sampled Sums of Binomial CoefficientsOnline Encyclopedia of Integer Sequences:
The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.Number of walks of length 2n+6 in the path graph P_7 from one end to the other.
Number of binary rooted trees of height n requiring 3 registers.
Triangle read by rows: T(n,k) is the number of full binary trees with n internal vertices and Strahler number k.
Sum of the Strahler numbers of all full binary trees with n internal vertices.
References:
| [1] | de Bruijn, N. G.; Knuth, D. E.; Rice, S. O., The average height of planted plane trees, (Read, R. C., Graph Theory and Computing (1972), Academic Press), 15-22 · Zbl 0247.05106 |
| [2] | Dacey, M. F., Summary of magnitude properties of topologically distinct channel networks and network patterns, (Merriam, Daniel F., Random Processes in Geology (1976), Springer-Verlag: Springer-Verlag Berlin), 16-38 |
| [3] | Delange, H., Sur la function sommatoire de la fonction somme des chiffres, Enseignement Math., 21, 1 (1975) · Zbl 0306.10005 |
| [4] | Ershov, A. P., On programming of arithmetic operations, CACM, 1, 8, 3-6 (1958) · Zbl 0086.33203 |
| [5] | Feller, W., An introduction to probability theory and its applications, Vol. 1 (1957), Wiley: Wiley New York · Zbl 0155.23101 |
| [6] | Flajolet, P.; Ramshaw, L., A note on Gray-code and odd-even merge (1977), to appear · Zbl 0447.68083 |
| [7] | Flajolet, P.; Françon, J.; Viennot, G.; Vuillemin, J., Arbres et Permutations: Combinatoire et Algorithmique (1978), in preparation |
| [8] | Jordan, R. E., Calculus of Finite Differences (1965), Chelsea: Chelsea New York · Zbl 0154.33901 |
| [9] | Kemp, R., The average number of registers to evaluate a binary tree optimally, Saarbrücken, University Report (1977) · Zbl 0395.68059 |
| [10] | Knuth, D. E., The Art of Computer Programming, Vol. 1 (1968), Addison-Wesley, 315 sq · Zbl 0191.17903 |
| [11] | Knuth, K. E., Structured programming with go to statements, Comput. Surveys, 6, 4, 216-302 (1974) · Zbl 0301.68014 |
| [12] | Kreweras, G., Sur les éventails de segments, Cahiers B.U.R.O., 15, 1-41 (1970) |
| [13] | Lucas, E., Theorie des Nombres (1891), Paris |
| [14] | McMahon, T. A., The mechanical design of trees, Sci. Amer., 233, 1, 92-102 (1975) |
| [15] | Nakata, I., On compiling algorithms for arithmetic expressions, CACM, 10, 8, 492-494 (1967) · Zbl 0154.41901 |
| [16] | Riordan, J., Combinatorial identities (1968), J. Wiley: J. Wiley New York · Zbl 0194.00502 |
| [17] | Sedgewick, R., Data movement in odd-even merging, Proc. of the Conference on Theoritical Computer Science (1977), Waterloo · Zbl 0418.68059 |
| [18] | Sethi, R.; Ullman, J. D., The generation of optimal code for arithmetic expressions, JACM, 17, 4, 715-728 (1970) · Zbl 0212.18802 |
| [19] | Shreve, R. L., Statistical Law of stream numbers, Geology, 74, 17-37 (1966) |
| [20] | Stevens, P. S., Patterns in Nature, ((1974), Atlantic Monthly Press, Little Brown and Co), 108-116 |
| [21] | Strahler, A. N., Hypsometric (area-altitude) analysis of erosional topography, Bulletin Geological Society of America, 63, 1117-1142 (1952) |
| [22] | van der Waerden, B. L., Ein einfaches Beispiel einer nicht-differenzierbaren stetigen Funktion, Math. Z, 32, 474-475 (1930) · JFM 56.0929.02 |
| [23] | Whittaker, E. T.; Watson, G. N., A Course of Modern Analysis (1902), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0108.26903 |
| [24] | Woldenberg, M. J., A structural taxonomy of spatial hierarchies, (Colston Papers, 22 (1970), Butterworths Scientific Publishers: Butterworths Scientific Publishers London), 147-175 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
