zbMATH — the first resource for mathematics

Propriétés de complexite pour une famille d’algorithmes de Markov. (French) Zbl 0368.68056

68Q45 Formal languages and automata
68W99 Algorithms in computer science
03D10 Turing machines and related notions
Full Text: EuDML
[1] 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] 2. P. AXT, On a Subrecursive hierarchy and Primitive Recursive Degrees, Trans. Amer. Math. Soc., vol. 92, 1959, p. 85-105. Zbl0087.01102 MR126377 · Zbl 0087.01102
[3] 3. A. V. AHO, J. E. HOPCROFT et J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison Wesley, 1974. Zbl0326.68005 MR413592 · Zbl 0326.68005
[4] 4. P. A. BEAVEN et D. W. LEWIN, An Associative Parallel Processing System for Non Numerical Computations, The computer Journal, vol. 15, n^\circ 4, 1972, p. 343-349. Zbl0245.68008 · Zbl 0245.68008
[5] 5. M. BLUM, A Machine Independant Theory of the Complexity of Recursive Functions, J. Assoc. Comp. Mach., vol. 14, 1967, p. 322-336. Zbl0155.01503 MR235912 · Zbl 0155.01503
[6] 6. A. CARACCIOLO DI FORINO, L. SPANEDDA et N. WOLKENSTEIN, Panon 1.B: a Programming Language for Symbol Manipulation, Calcolo, 1966, p. 245-255. Zbl0221.68031 MR202608 · Zbl 0221.68031
[7] 7. A. CARACCIOLO DI FORINO, Generalized Markov Algorithms and Automata, Automata theory, ed., CAIANIELLO, Academic Press New York. Zbl0192.06302 · Zbl 0192.06302
[8] 8. S. A. COOK et R. A. RECKOW, Time Bounded Rondom Access Machines, J. Comp. System. Sc. vol.7, 1973, p. 354-375. Zbl0284.68038 MR327074 · Zbl 0284.68038
[9] 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. Zbl0117.12201 · Zbl 0117.12201
[10] 10. B. A. GALLER et A. J. PERLIS, A view of Programming Languages, Addison Wesley, 1970. Zbl0234.68002 MR272223 · Zbl 0234.68002
[11] 11. A. GRZEGORCZYCK, Some Classes of Recursive Functions, Rozprawy Matematyczne, vol. 4, Warsaw, 1953, p. 1-45 Zbl0052.24902 MR60426 · Zbl 0052.24902
[12] 12. J. HARTMANIS, Computational Complexity of One Tape Turing Machine Computations, J. Assoc. Comp. Mach., vol. 15, 1968, p. 325-339. Zbl0162.31703 MR252127 · Zbl 0162.31703
[13] 13. J. E. HOPCROFT et J. D. ULLMAN, Formal Languages and their Relations to Automata, Addison Wesley, 1969. Zbl0196.01701 MR237243 · Zbl 0196.01701
[14] 14. J. KATZENELSON, The Markov Algorithm as a Language Parser; Linear Bounds, J. Comp. System Sc., vol. 6, 1972, p. 465-478. Zbl0247.68030 MR315941 · Zbl 0247.68030
[15] 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. Zbl0323.68030 MR387038 · Zbl 0323.68030
[16] 16. G. LEONI et R. SPRUGNOLI, Some Relations between Markov Algorithms and Formal Languages, Inst. Sc. Infor. Report, S-76-4, 1976, Pisa. MR505347 · Zbl 0374.68043
[17] 17. A. A. MARKOV, Theory of Algorithms, Traduction anglaise : Israël program for scientific translations, Jérusalem, 1961. MR181560
[18] 18. G. MICHEL, Thèse de 3e cycle, Université de Rennes, 1975.
[19] 19. J. M. MORRIS et V. R. PRATT, A Linear Pattern Matching Algorithm, Technical Report n^\circ 40, Univ. of California, Berkeley, 1970.
[20] 20. M. PAGET, Applications des algorithmes de Markov à la complexité des programmes, Thèse de 3e cycle, Institut de Programmation, Université Paris-VI, 1976. · Zbl 0332.02041
[21] 21. R. W. RITCHIE, Class of Predictably Computable Functions, Trans. A.M.S., vol. 106, 1963. Zbl0107.01001 MR158822 · Zbl 0107.01001
[22] 22. A. VAN WIJNGAARDEN, Recursive Definition of Syntax and Semanticsin Proc. I.F.I.P., 1964, North Holland, Amsterdam, 1966, p. 13-24.
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.