×

zbMATH — the first resource for mathematics

Tours de Hanoï et automates. (Towers of Hanoi and automata). (French) Zbl 0701.68036
Summary: We show that the sequence of moves in the classical towers of Hanoï algorithm can be generated by a finite automaton. This throws light on the arithmetical properties of this algorithm and contains in particular all the “periodicity” results. Similar methods are used to study the intrinsically more complex problem of “cyclic” Hanoï towers.

MSC:
68W10 Parallel algorithms in computer science
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] 1. A. AHO, J. HOPCROFT et J. ULLMANN, The Design and Analysis of Computers Algorithms, Addison-Wesley, Reading, MA, 1974, Zbl0326.68005 MR413592 · Zbl 0326.68005
[2] 2. J. ARSAC, Le construction de programmes structurés, Dunod, Paris, 1977. Zbl0451.68014 · Zbl 0451.68014
[3] 3. J. ARSAC, Les bases de la programmation, Dunod, Paris, 1983. Zbl0624.68004 · Zbl 0624.68004
[4] 4. J. ARSAC, Jeux et casse-tête à programmer, Dunod, Paris, 1985.
[5] 5. M. D. ATKINSON, The Cyclic Towers of Hanoï, Inform. Process. Lett., vol. 13, 1981, p. 118-119. Zbl0467.68083 MR645457 · Zbl 0467.68083 · doi:10.1016/0020-0190(81)90123-X
[6] 6. W. R. BALL, Mathematical Recreations and Essays, McMillan, London, 1892. Voir aussi · JFM 65.1075.02
[7] W. R. BALL et H. S. M. COXETER, Mathematical Recreations and Essays, University of Toronto Press, Toronto, 1974, p. 316-317. MR351741
[8] 7. D. T. BARNARD, The Towers of Hanoï : an Exercise in Non Recursive Algorithm Development, Technical Report 80-103, Dept. of Computing and Information Science, Queen’s University, 1980.
[9] 8. Br. A. BROUSSEAU, Towers of Hanoï with More Pegs, J. Recreat. Math., vol. 8, (3), 1976, p. 165-176. Zbl0332.05003 · Zbl 0332.05003
[10] 9. P. BUNEMAN et L. LEVY, The Towers of Hanoï Problem, Inform. Process. Lett., vol. 10, 1980, p. 243-244. Zbl0439.05010 MR585392 · Zbl 0439.05010 · doi:10.1016/0020-0190(80)90150-7
[11] 10. G. CHRISTOL, T. KAMAE, M. MENDÈS FRANCE et G. RAUZY, Suites algébriques, automates et substitutions, Bull. Soc. Math. France, vol. 108, 1980, p. 401-419. Zbl0472.10035 MR614317 · Zbl 0472.10035 · numdam:BSMF_1980__108__401_0 · eudml:87381
[12] 11. N. CLAUS (anagramme de Lucas), La tour de Hanoï, jeu de calcul, Revue Science et Nature, vol. 1, n^\circ 8, 1884, p. 127-128.
[13] 12. A. COBHAM, Uniform Tag Sequences, Math. Syst. Theory, vol. 6, 1972, p. 164-192. Zbl0253.02029 MR457011 · Zbl 0253.02029 · doi:10.1007/BF01706087
[14] 13. P. CULL et E. ECKLUND, Towers of Hanoï and Analysis of Algorithms, Amer. Math. Monthly, vol. 92, (6), June/July 1985. Zbl0589.90086 MR795250 · Zbl 0589.90086 · doi:10.2307/2322448
[15] 14. H. E. DUDENEY, The Canterbury Puzzles, Thos. Nelson & Sons, 1919, réédition Dovers Publications Ltd, New York, 1958.
[16] 15. J. ENGELFRIET, The Trees of Hanoï, 1981, preprint.
[17] 16. M. C. ER, A Representation Approach to the Towers of Hanoï Problem, The Comput. J., 1982, p. 442-447. Zbl0493.90100 · Zbl 0493.90100 · doi:10.1093/comjnl/25.4.442
[18] 17. M. C. ER, An Iterative Solution to the Cyclic Towers of Hanoï Problem, Technical Report, Dept. of Computing Science, University of Wollogang, 1982.
[19] 18. M. C. ER, The Cyclic Towers of Hanoï : a Generalization, Technical Report, Dept. of Computing Science, University of Wollogang, 1982.
[20] 19. M. C. ER, A Generalization of the Cyclic Towers of Hanoï, Technical Report, Dept. of Computing Science, University of Wollogang, 1982.
[21] 20. M. C. ER, Towers of Hanoï with Black and White Discs, J. Inform. Optim. Sci., vol. 6, (1), 1985, p. 87-93. MR793864
[22] 21. M. C. ER, The Towers of Hanoï and Binary Numerals, J. Inform. Optim. Sci., vol. 6, (2), 1985, p. 147-152. Zbl0578.68054 MR796981 · Zbl 0578.68054
[23] 22. M. C. ER, The Complexity of the Generalised Cyclic Towers of Hanoï, J. Algorithms, vol. 6, (3), 1985, p. 351-358. Zbl0576.68036 MR800725 · Zbl 0576.68036 · doi:10.1016/0196-6774(85)90004-5
[24] 23. J.-C. FOURNIER, Pour en finir avec la dérécursivation du problème des tours de Hanoï, Actes Journée A.F.C.E.T. Combinatoire, Lyon-I, 1985.
[25] 24. J. S. FRAME et B. M. STEWART, Solution of Problem n^\circ 3918, Amer. Math. Monthly, vol. 48, 1941, p. 216-219. MR1525110
[26] 25. M. GARDNER, Mathemaiical Puzzles and Diversions, Simon & Schuster, New York, 1958, p. 55-62.
[27] 26. M. GARDNER, Mathematical Games : the CuriousPropertiesof the Gray Code and How it Can Be Used to Solve Puzzles, Sci. Amer., août 1972, p. 106-109.
[28] 27. C. GERETY et P. CULL, Time Complexity of the Towers of Hanoï Problem, SIGACT News, vol. 18, (1), 1986. Zbl0621.68029 · Zbl 0621.68029
[29] 28. J. HARDOUIN-DUPARC, Génération de mots par des piles d’automates, 1985, preprint.
[30] 29. P. J. HAYES, A Note on the Towers of Hanoï Problem, The Comput. J., 1977, p. 282-285. Zbl0362.68057 · Zbl 0362.68057 · doi:10.1093/comjnl/20.3.282
[31] 30. K. JACOBS et M. KEANE, On 0-1 Sequences of Toeplitz Type, Z. Warsch. Geb., vol. 13, 1969, p. 123-131. Zbl0195.52703 MR255766 · Zbl 0195.52703 · doi:10.1007/BF00537017
[32] 31. M. S. KRISHNAMOORTHY et S. BISWAS, The Generalized Towers of Hanoï (preprint), 1978.
[33] 32. I. LAVALLÉE, Note sur le problème des tours de Hanoï, Rev. Roumaine Math. pures et appl., vol. 30, 1985, p. 433-438. Zbl0577.05010 MR802766 · Zbl 0577.05010
[34] 33. B. MEYER et C. BAUDOUIN, Méthodes de programmation, Eyrolles, Paris, 3e édition, 1984. Zbl0407.68002 · Zbl 0407.68002
[35] 34. S. MINKER, Three Variations on the Towers of Hanoï Problem, S. M. Thesis, University of Pennsylvania, 1983.
[36] 35. H. PARTSCH et P. PEPPER, A Family of Rules for Recursion Removal, 1986, preprint. MR443407 · Zbl 0345.68011
[37] 36. G. RAUZY, Cours de D.E.A. (communication privée), 1986.
[38] 37. J. S. ROHL, Recursion via Pascal, Cambridge University Press, 1984. Zbl0547.68003 · Zbl 0547.68003 · doi:10.1017/CBO9781139171793
[39] 38. T. ROTH, The Tower of Brahma Revisited, J. Recreat. Math., vol. 7, n^\circ 2, 1974, p. 116-119.
[40] 39. A. SAINTE-LAGUE, Avec des nombres et des lignes, Vuibert, Paris, 1942, p. 71-78.
[41] 40. F. SCHUH, The Master Book of Mathematical Recreations, Dover Publications, Inc., New York, 1968, p. 119-121. Zbl0191.27406 · Zbl 0191.27406
[42] 41. T. R. WALSH, The Towers of Hanoï Revisited: Moving the Rings by Counting the Moves, Inform. Process. Lett., vol. 15, 1982, p. 64-67. Zbl0487.90099 MR675870 · Zbl 0487.90099 · doi:10.1016/0020-0190(82)90108-9
[43] 42. D. WOOD, The Towers of Brahma and Hanoï Revisited, J. Recreat. Math., vol. 14, n^\circ 1, 1981, p. 17-24. Zbl0486.05014 MR629340 · Zbl 0486.05014
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.