On the average number of registers needed to evaluate a special class of backtrack trees

U. Trier

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)

  • Volume: 27, Issue: 6, page 541-554
  • ISSN: 0988-3754

How to cite

top

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 27.6 (1993): 541-554. <http://eudml.org/doc/92465>.

@article{Trier1993,
author = {Trier, U.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {binary trees},
language = {eng},
number = {6},
pages = {541-554},
publisher = {EDP-Sciences},
title = {On the average number of registers needed to evaluate a special class of backtrack trees},
url = {http://eudml.org/doc/92465},
volume = {27},
year = {1993},
}

TY - JOUR
AU - Trier, U.
TI - On the average number of registers needed to evaluate a special class of backtrack trees
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1993
PB - EDP-Sciences
VL - 27
IS - 6
SP - 541
EP - 554
LA - eng
KW - binary trees
UR - http://eudml.org/doc/92465
ER -

References

top
  1. 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. Zbl0407.68057MR535127
  2. 2. R. L. GRAHAM, D. E. KNUTH and O. PATASHNIK, ConcreteMathematics, Addison-Wesley, Reading, Mass. 1988. Zbl0668.00003
  3. 3. R. KEMP, The Average Number of Registers Needed to Evaluate a Binary Tree Optimally, Acta Inf., 1979, 11, pp. 363-372. Zbl0395.68059MR533482
  4. 4. R. KEMP, The Expected Additive Weight of Trees, Acta Inf., 1989, 26, pp. 7-740. Zbl0685.68023MR1021787
  5. 5. R. KEMP, The Analysis of a Special Class of Backtrack Trees, preprint Johann Wolfgang Goethe-Universität Frankfurt, 1991. 
  6. 6. R. KEMP, On the Stacksize of a Class of Backtrack Trees, preprint Johann Wolfgang Goethe-Universität Frankfurt, 1991. 
  7. 7. D. E. KNUTH, The Art of Computer Programming, Vol. 1, (2nd éd.), Addison-Wesley, Reading, Mass., 1973. Zbl0302.68010MR378456
  8. 8. A. MEIR and J. W. MOON, On the Altitude of Nodes in Random Trees, Can. J. Math., 1978, 30 pp. 997-1015. Zbl0394.05015MR506256
  9. 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. 10. P. W. PURDOM, Tree Size by Partial Backtracking, SIAM J. Comput., 1978, 7 (4) pp. 481-491. Zbl0386.68044MR508608
  11. 11. U. TRIER, Additive Weights of a Special Class of Nonuniformly Distributed Backtrack Trees, Inform. Proc. Letters, 1992, 42, pp. 67-76. Zbl0780.68068MR1170871

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.