Combined complexity classes for finite functions
Breitbart, Y. ; Lewis, F. D.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979), p. 87-97 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1979-01-01
@article{ITA_1979__13_1_87_0,
     author = {Breitbart, Y. and Lewis, F. D.},
     title = {Combined complexity classes for finite functions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {13},
     year = {1979},
     pages = {87-97},
     mrnumber = {525459},
     zbl = {0414.68023},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1979__13_1_87_0}
}

Breitbart, Y.; Lewis, F. D. Combined complexity classes for finite functions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979) pp. 87-97. http://gdmltest.u-ga.fr/item/ITA_1979__13_1_87_0/

1. Ya. M. Barzdin, The Complexity of Programs Recongizing Finite Subsets of Recursively Enumerable Sets, Doklady Akad. Nauk, Vol. 182, 1968, pp. 1249-1252 (in Russian). | MR 236009 | Zbl 0193.31601

2. Y. Breitbart, Tape Complexity of the Predicate to be a Complex Boolean Function, in preparation.

3. J. Hartmanis and R. E. Stearns, On the Computational Complexity of Algorithms, Trans. Amer. Math. Soc., 117, 1965, pp. 285-306. | MR 170805 | Zbl 0131.15404

4. J. E. Hopcroft and J. D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley, 1969. | MR 237243 | Zbl 0196.01701

5. M. I. Kanovich and N. V. Petri Some Theorems About Complexity of Normal Algorithms and Computations, Dokl. Akad Nauk, S.S.S.R., Vol. 184, No. 6, 1969, pp. 1275-1276 (in Russian). | MR 242676 | Zbl 0181.31303

6. V. Kuzmin, Evaluation of Boolean Functions by Finite Automata, Normal Algorithms, and Turing Machines, Prob. of Cybernetics, Vol. 13, 1965, pp. 75-96. | MR 199062

7. F. D. Lewis, Classes of Recursive Functions and Their Index Sets, Zeit. f. Math. Logiku. Grund. d. Math., Vol. 17, 1971. | MR 294130 | Zbl 0229.02035

8. F. D. Lewis, The Enumerability and Invariance of Complexity Classes, J. Comp. System Sc., Vol. 5, 1971, pp. 286-303. | MR 278951 | Zbl 0215.04701

9. O. B. Lupanov, Ob odnom Methode Syntesa Schm, Izv. VUS'ov Radiofizika, Vol. 1, 1958, pp. 120-140.

10. O. B. Lupanov, One Approach to Synthesis of Control Systems-Principle of Local Coding, Prob. of Cybernetics, Vol. 14, 1965, pp. 31-110. | MR 201219 | Zbl 0256.94043

11. A. A. Markov, Normal Algorithms for Computation of Boolean Functions, Izv. Akad.Nauk, S.S.S.R., Vol. 31, 1967, pp. 161 (in Russian). | MR 210587 | Zbl 0148.24803

12. N. V. Petri, On Algorithms Related to Predicate and Boolean Functions, Dokl. Akad Nauk, S.S.S.R., Vol. 185, No. 1, 1969, pp. 37-39 (in Russian). | MR 250881 | Zbl 0193.31501

13. N. Pippenger, The Realization of Monotone Boolean Functions, A.C.M. Sym. on Theory of Comp., 1976, pp. 204-211. | MR 434654 | Zbl 0366.94050

14. H. Jr. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, NY, 1967. | MR 224462 | Zbl 0183.01401

15. J. Savage, The Complexity of Computing, 1976, Wiley and Sons, NY. | MR 495205 | Zbl 0391.68025

16. C. P. Schnorr, The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Infor., Vol. 7, 1976, pp. 95-107. | MR 421889 | Zbl 0338.02019

17. L. A. Sholomov, Information Complexity Problems of Minimal Realization of Boolean Functions by Combinational Schemas, Prob. of Cybernetics, Vol. 26, 1973, pp. 207-256.

18. B. A. Trachtenbrot, On Problems Solvable by Successive Trials, Math. Found. of Comp. Sc., 1975 (Lect. Notes in Comp. Science n° 32, Springer-Verlag, pp. 125-137). | MR 395329 | Zbl 0357.68060

19. S. V. Yablonski, On Algorithmic Difficulties in Synthesis of Minimal Schemas, Prob. of Cybernetics, Vol. 2, 1959, pp. 75-121. | MR 129088