Une généralisation de la notion d’ensemble immune. (French) Zbl 0283.02034


03D25 Recursively (computably) enumerable sets and degrees
Full Text: EuDML


[1] ROGERS H., Theory of Recursive Functions and Effective computability, McGraw Hill (1966). Zbl0183.01401 MR224462 · Zbl 0183.01401
[2] GRZEGORCZYK A., Some Classes of Recursive Function, Rozprawy Maternatyczne, pp. 1-46 (1953). Zbl0052.24902 MR60426 · Zbl 0052.24902
[3] PETER R., Recursive Functions, Academic Press (1966). Zbl0154.00601 MR219414 · Zbl 0154.00601
[4] BLUM M., A machine-Independent Theory of the Complexity of Recursive Functions, JACM, vol. 14, n^\circ 2, Appril (1967), pp. 322-336. Zbl0155.01503 MR235912 · Zbl 0155.01503 · doi:10.1145/321386.321395
[5] FLAJOLET P. et STEYAERT J. M., Generalised Immune Sets, Rapport IRIA (1973).
[6] CONSTABLE R., Hierarchy Theorems for Axiomatic Complexity, Computational Complexity, pp. 37-63, edited by Randall Rustin-Algorithmics Press Inc (1973).
[7] FLAJOLET P. et STEYAERT J. M., Une Formalisation de la Notion d’Algorithme de Tri non Récurrent. Thèse de 3e cycle, Paris VII (1973).
[8] CUDIA D., The degree hierarchy of undecidable problems of formal grammars, ACM-SIGACT Symposium (1970). · Zbl 0169.31302
[9] LEWIS F. D., On Unsolvability in Subrecursive Classes of Predicates, Harvard University report (1972). · Zbl 0316.02050
[10] MEYER A. et RITCHIE D., Computational Complexity and Program Structure, IBM research report RC 1817 (1967).
[11] IBARRA O., On two way Multihead Automata, JCSS 7, 28-36 (1973). Zbl0256.68028 MR408317 · Zbl 0256.68028 · doi:10.1016/S0022-0000(73)80048-0
[12] ROSENBERG A., On multihead Finite Automata, IBM Journal (1966), 388-394. Zbl0168.01303 · Zbl 0168.01303 · doi:10.1147/rd.105.0388
[13] FLAJOLET P. et STEYAERT J. M., Decision Problems for Multihead Finite Automata. Proceedings of MFCS Symposium, pp. 225-230 (1973). MR408315
[14] MEYER A. et FISCHER M., Economy of Description by Automata, Grammars and Formal Systems. Conference Record (1971). 12tl Annual Sympon Switching an Automata Theory, pp. 188-191.
[15] MEYER A.Program Size, in Restricted Programming Languages, Information and Control, 21, 382-394 (1972). Zbl0301.68019 MR321343 · Zbl 0301.68019 · doi:10.1016/S0019-9958(72)90592-X
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.