Propriétés de complexité pour une famille d'algorithmes de Markov
Paget, Martine
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 12 (1978), p. 15-32 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1978__12_1_15_0,
     author = {Paget, Martine},
     title = {Propri\'et\'es de complexit\'e pour une famille d'algorithmes de Markov},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {12},
     year = {1978},
     pages = {15-32},
     mrnumber = {495201},
     zbl = {0368.68056},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1978__12_1_15_0}
}

Paget, Martine. Propriétés de complexité pour une famille d'algorithmes de Markov. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 12 (1978) pp. 15-32. http://gdmltest.u-ga.fr/item/ITA_1978__12_1_15_0/

1. G. Aguzzi, F. Cesarini et R. Pinzani, Automatic Tree Structures Processingin Proceedings of Colloque de Lille : Lesarbres en Algèbre et en programmation, Lille, 1976.

2. P. Axt, On a Subrecursive hierarchy and Primitive Recursive Degrees, Trans. Amer. Math. Soc., vol. 92, 1959, p. 85-105. | MR 126377 | Zbl 0087.01102

3. A. V. Aho, J. E. Hopcroft et J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison Wesley, 1974. | MR 413592 | Zbl 0326.68005

4. P. A. Beaven et D. W. Lewin, An Associative Parallel Processing System for Non Numerical Computations, The computer Journal, vol. 15, n° 4, 1972, p. 343-349. | Zbl 0245.68008

5. M. Blum, A Machine Independant Theory of the Complexity of Recursive Functions, J. Assoc. Comp. Mach., vol. 14, 1967, p. 322-336. | MR 235912 | Zbl 0155.01503

6. A. Caracciolo Di Forino, L. Spanedda et N. Wolkenstein, Panon 1.B: a Programming Language for Symbol Manipulation, Calcolo, 1966, p. 245-255. | MR 202608 | Zbl 0221.68031

7. A. Caracciolo Di Forino, Generalized Markov Algorithms and Automata, Automata theory, ed., CAIANIELLO, Academic Press New York. | Zbl 0192.06302

8. S. A. Cook et R. A. Reckow, Time Bounded Rondom Access Machines, J. Comp. System. Sc. vol.7, 1973, p. 354-375. | MR 327074 | Zbl 0284.68038

9. D. J. Farber, R. E. Griswold et I. P. Polonsky, Snobol, a String Manipulation Language, J. Assoc. Comp. Mach., vol. 11, 1964, p. 21-30. | Zbl 0117.12201

10. B. A. Galler et A. J. Perlis, A view of Programming Languages, Addison Wesley, 1970. | MR 272223 | Zbl 0234.68002

11. A. Grzegorczyck, Some Classes of Recursive Functions, Rozprawy Matematyczne, vol. 4, Warsaw, 1953, p. 1-45 | MR 60426 | Zbl 0052.24902

12. J. Hartmanis, Computational Complexity of One Tape Turing Machine Computations, J. Assoc. Comp. Mach., vol. 15, 1968, p. 325-339. | MR 252127 | Zbl 0162.31703

13. J. E. Hopcroft et J. D. Ullman, Formal Languages and their Relations to Automata, Addison Wesley, 1969. | MR 237243 | Zbl 0196.01701

14. J. Katzenelson, The Markov Algorithm as a Language Parser; Linear Bounds, J. Comp. System Sc., vol. 6, 1972, p. 465-478. | MR 315941 | Zbl 0247.68030

15. M. R. Lagana, G. Leoni, R. Pinzani et R. Sprugnoli, Improvements in the Exexution of Markov Algorithms, Bull. Math. Ital., vol. 11, 1975, p. 473-489. | MR 387038 | Zbl 0323.68030

16. G. Leoni et R. Sprugnoli, Some Relations between Markov Algorithms and Formal Languages, Inst. Sc. Infor. Report, S-76-4, 1976, Pisa. | MR 505347

17. A. A. Markov, Theory of Algorithms, Traduction anglaise : Israël program for scientific translations, Jérusalem, 1961. | MR 181560

18. G. Michel, Thèse de 3e cycle, Université de Rennes, 1975.

19. J. M. Morris et V. R. Pratt, A Linear Pattern Matching Algorithm, Technical Report n° 40, Univ. of California, Berkeley, 1970.

20. M. Paget, Applications des algorithmes de Markov à la complexité des programmes, Thèse de 3e cycle, Institut de Programmation, Université Paris-VI, 1976.

21. R. W. Ritchie, Class of Predictably Computable Functions, Trans. A.M.S., vol. 106, 1963. | MR 158822 | Zbl 0107.01001

22. A. Van Wijngaarden, Recursive Definition of Syntax and Semanticsin Proc. I.F.I.P., 1964, North Holland, Amsterdam, 1966, p. 13-24.