Combined complexity classes for finite functions
RAIRO. Informatique théorique, Tome 13 (1979) no. 1, pp. 87-97. 
@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/}
}
TY  - JOUR
AU  - Breitbart, Y.
AU  - Lewis, F. D.
TI  - Combined complexity classes for finite functions
JO  - RAIRO. Informatique théorique
PY  - 1979
SP  - 87
EP  - 97
VL  - 13
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1979__13_1_87_0/
LA  - en
ID  - ITA_1979__13_1_87_0
ER  - 
%0 Journal Article
%A Breitbart, Y.
%A Lewis, F. D.
%T Combined complexity classes for finite functions
%J RAIRO. Informatique théorique
%D 1979
%P 87-97
%V 13
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1979__13_1_87_0/
%G en
%F ITA_1979__13_1_87_0
Breitbart, Y.; Lewis, F. D. Combined complexity classes for finite functions. RAIRO. Informatique théorique, Tome 13 (1979) no. 1, pp. 87-97. http://archive.numdam.org/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 | Zbl

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 | Zbl

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

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 | Zbl

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

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

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

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 | Zbl

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 | Zbl

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 | Zbl

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

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

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

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

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 | Zbl

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