@article{ITA_1979__13_1_87_0, author = {Breitbart, Y. and Lewis, F. D.}, title = {Combined complexity classes for finite functions}, journal = {RAIRO. Informatique th\'eorique}, pages = {87--97}, publisher = {EDP-Sciences}, volume = {13}, number = {1}, year = {1979}, mrnumber = {525459}, zbl = {0414.68023}, language = {en}, url = {http://archive.numdam.org/item/ITA_1979__13_1_87_0/} }
Breitbart, Y.; Lewis, F. D. Combined complexity classes for finite functions. RAIRO. Informatique théorique, Volume 13 (1979) no. 1, pp. 87-97. http://archive.numdam.org/item/ITA_1979__13_1_87_0/
1. The Complexity of Programs Recongizing Finite Subsets of Recursively Enumerable Sets, Doklady Akad. Nauk, Vol. 182, 1968, pp. 1249-1252 (in Russian). | MR | Zbl
,2. Tape Complexity of the Predicate to be a Complex Boolean Function, in preparation.
,3. On the Computational Complexity of Algorithms, Trans. Amer. Math. Soc., 117, 1965, pp. 285-306. | MR | Zbl
and ,4. Formal Languages and their Relation to Automata, Addison-Wesley, 1969. | MR | Zbl
and ,5. 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 | Zbl
and6. Evaluation of Boolean Functions by Finite Automata, Normal Algorithms, and Turing Machines, Prob. of Cybernetics, Vol. 13, 1965, pp. 75-96. | MR
,7. Classes of Recursive Functions and Their Index Sets, Zeit. f. Math. Logiku. Grund. d. Math., Vol. 17, 1971. | MR | Zbl
,8. The Enumerability and Invariance of Complexity Classes, J. Comp. System Sc., Vol. 5, 1971, pp. 286-303. | MR | Zbl
,9. Ob odnom Methode Syntesa Schm, Izv. VUS'ov Radiofizika, Vol. 1, 1958, pp. 120-140.
,10. One Approach to Synthesis of Control Systems-Principle of Local Coding, Prob. of Cybernetics, Vol. 14, 1965, pp. 31-110. | MR | Zbl
,11. Normal Algorithms for Computation of Boolean Functions, Izv. Akad.Nauk, S.S.S.R., Vol. 31, 1967, pp. 161 (in Russian). | MR | Zbl
,12. 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 | Zbl
,13. The Realization of Monotone Boolean Functions, A.C.M. Sym. on Theory of Comp., 1976, pp. 204-211. | MR | Zbl
,14. Theory of Recursive Functions and Effective Computability, McGraw-Hill, NY, 1967. | MR | Zbl
,15. The Complexity of Computing, 1976, Wiley and Sons, NY. | MR | Zbl
,16. The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Infor., Vol. 7, 1976, pp. 95-107. | MR | Zbl
,17. Information Complexity Problems of Minimal Realization of Boolean Functions by Combinational Schemas, Prob. of Cybernetics, Vol. 26, 1973, pp. 207-256.
,18. 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 | Zbl
,19. On Algorithmic Difficulties in Synthesis of Minimal Schemas, Prob. of Cybernetics, Vol. 2, 1959, pp. 75-121. | MR
,