Quelques remarques sur la complexité des algorithmes
Werner, G.
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 4 (1970), p. 33-50 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1970-01-01
@article{M2AN_1970__4_2_33_0,
     author = {Werner, G.},
     title = {Quelques remarques sur la complexit\'e des algorithmes},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     volume = {4},
     year = {1970},
     pages = {33-50},
     mrnumber = {297574},
     zbl = {0209.03302},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/M2AN_1970__4_2_33_0}
}

Werner, G. Quelques remarques sur la complexité des algorithmes. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 4 (1970) pp. 33-50. http://gdmltest.u-ga.fr/item/M2AN_1970__4_2_33_0/

[1] J. Hartmanis, R. E. Stearns. « On the Computational Complexity of Algorithms » Trans. Amer. Math. Soc., 117, pp. 285-306 (1965). | MR 170805 | Zbl 0131.15404

[2] P. M. Lewis Ii, R. E. Stearns et Hartmanis J. « Memory bounds for the recognition of context-free and context-sensitive languages », 1965,IEEE Conference Reord on Switching Circuit Theory and Logical Design, pp. 191-202, IEEE, New York (1965). | Zbl 0272.68054

[3] J. Hartmanis, « Tape-Reversal Bounded Turing Machine Computations », Journal of Computer and System Sciences 2, Nr 2, pp. 117-135 (1968). | MR 243947 | Zbl 0259.68020

[4] R. W. Ritchie, « Classes of Predictably Computable Functions », Trans. Amer. Math. Soc, 106, pp. 139-173 (1963). | MR 158822 | Zbl 0107.01001

[5] M. O. Rabin, « Degrees of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets », Technical Reporter Nr 2, Hebrew University, Jérusalem, (1960).

[6] Manuel Blum, « A Machine-Independent Theory of the Complexity of Recursive Functions », Journal A.C.M., avril 1967, vol. 14, Nr 2, pp. 322-336. | MR 235912

[7] Manuel Blum, « Recursive Function Theory and Speed of Computation », Canadian Math. Bull. 9 (1966), pp. 745-750. | Zbl 0158.24904

[8] Dieter Rödding, « Klassen rekursiver Funktionen », Lecture Notes in Math. 70, 1968, Springer-Verlag, Berlin, pp. 159-222. | MR 237335 | Zbl 0212.32802

[9] S. C. Kleene, « Extension of an Effectively Generated Class of Functions by Enumeration », Colloquium Math. VI (1958), pp. 67-78. | MR 118672 | Zbl 0085.24602

[10] Hartley Rogers, Theory of Recursive Functions and Effective Computability, Mac Graw-Hill Book Company, New York, 1967. | MR 224462 | Zbl 0183.01401