On the average number of registers needed to evaluate a special class of backtrack trees
Trier, U.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993), p. 541-554 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1993__27_6_541_0,
     author = {Trier, U.},
     title = {On the average number of registers needed to evaluate a special class of backtrack trees},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {27},
     year = {1993},
     pages = {541-554},
     mrnumber = {1258751},
     zbl = {0809.68104},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1993__27_6_541_0}
}

Trier, U. On the average number of registers needed to evaluate a special class of backtrack trees. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) pp. 541-554. http://gdmltest.u-ga.fr/item/ITA_1993__27_6_541_0/

1. Ph. Flajolet, J.-C. Raoult and J. Vuillemin, The Number of Registers Required to Evaluate Arithmetic Expressions, Theoret. Comp. Sci. 1979, 9, pp. 99-125. | MR 535127 | Zbl 0407.68057

2. R. L. Graham, D. E. Knuth and O. Patashnik, ConcreteMathematics, Addison-Wesley, Reading, Mass. 1988. | Zbl 0668.00003

3. R. Kemp, The Average Number of Registers Needed to Evaluate a Binary Tree Optimally, Acta Inf., 1979, 11, pp. 363-372. | MR 533482 | Zbl 0395.68059

4. R. Kemp, The Expected Additive Weight of Trees, Acta Inf., 1989, 26, pp. 7-740. | MR 1021787 | Zbl 0685.68023

5. R. Kemp, The Analysis of a Special Class of Backtrack Trees, preprint Johann Wolfgang Goethe-Universität Frankfurt, 1991.

6. R. Kemp, On the Stacksize of a Class of Backtrack Trees, preprint Johann Wolfgang Goethe-Universität Frankfurt, 1991.

7. D. E. Knuth, The Art of Computer Programming, Vol. 1, (2nd éd.), Addison-Wesley, Reading, Mass., 1973. | MR 378456

8. A. Meir and J. W. Moon, On the Altitude of Nodes in Random Trees, Can. J. Math., 1978, 30 pp. 997-1015. | MR 506256 | Zbl 0394.05015

9. H. Prodinger, Détermination de certains paramètres d'arbres binaires à l'aide de méthodes analytiques, Laboratoire de Recherche en Informatique, Université Paris 11, 91405 Orsay cedex-France, Rapport de Recherche N° 177, 1984.

10. P. W. Purdom, Tree Size by Partial Backtracking, SIAM J. Comput., 1978, 7 (4) pp. 481-491. | MR 508608 | Zbl 0386.68044

11. U. Trier, Additive Weights of a Special Class of Nonuniformly Distributed Backtrack Trees, Inform. Proc. Letters, 1992, 42, pp. 67-76. | MR 1170871 | Zbl 0780.68068