{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T09:42:44Z","timestamp":1648978964958},"reference-count":19,"publisher":"EDP Sciences","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO. Inform. th\u00e9or."],"published-print":{"date-parts":[[1979]]},"DOI":"10.1051\/ita\/1979130100871","type":"journal-article","created":{"date-parts":[[2017,2,6]],"date-time":"2017-02-06T15:44:48Z","timestamp":1486395888000},"page":"87-97","source":"Crossref","is-referenced-by-count":0,"title":["Combined complexity classes for finite functions"],"prefix":"10.1051","volume":"13","author":[{"given":"Y.","family":"Breitbart","sequence":"first","affiliation":[]},{"given":"F. D.","family":"Lewis","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"R1","unstructured":"1. BARZDIN Ya. M., The Complexity of Programs Recongizing Finite Subsets of Recursively Enumerable Sets, Doklady Akad. Nauk, Vol. 182, 1968, pp. 1249-1252 (in Russian).2360090193.31601"},{"key":"R2","unstructured":"2. BREITBART Y., Tape Complexity of the Predicate to be a Complex Boolean Function, in preparation."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"3. HARTMANIS J. and STEARNS R. E., On the Computational Complexity of Algorithms, Trans. Amer. Math. Soc., 117, 1965, pp. 285-306.1708050131.15404","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"R4","unstructured":"4. HOPCROFT J. E. and ULLMAN J. D., Formal Languages and their Relation to Automata, Addison-Wesley, 1969.2372430196.01701"},{"key":"R5","unstructured":"5. KANOVICH M. I. and PETRI N. V. 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).2426760181.31303"},{"key":"R6","unstructured":"6. KUZMIN V., Evaluation of Boolean Functions by Finite Automata, Normal Algorithms, and Turing Machines, Prob. of Cybernetics, Vol. 13, 1965, pp. 75-96.199062"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"7. LEWIS F. D., Classes of Recursive Functions and Their Index Sets, Zeit. f. Math. Logiku. Grund. d. Math., Vol. 17, 1971.2941300229.02035","DOI":"10.1002\/malq.19710170134"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"8. LEWIS F. D., The Enumerability and Invariance of Complexity Classes, J. Comp. System Sc., Vol. 5, 1971, pp. 286-303.2789510215.04701","DOI":"10.1016\/S0022-0000(71)80037-5"},{"key":"R9","unstructured":"9. LUPANOV O. B., Ob odnom Methode Syntesa Schm, Izv. VUS'ov Radiofizika, Vol. 1, 1958, pp. 120-140."},{"key":"R10","unstructured":"10. LUPANOV O. B., One Approach to Synthesis of Control Systems-Principle of Local Coding, Prob. of Cybernetics, Vol. 14, 1965, pp. 31-110.2012190256.94043"},{"key":"R11","unstructured":"11. MARKOV A. A., Normal Algorithms for Computation of Boolean Functions, Izv. Akad.Nauk, S.S.S.R., Vol. 31, 1967, pp. 161 (in Russian).2105870148.24803"},{"key":"R12","unstructured":"12. PETRI N. V., 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).2508810193.31501"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"13. PIPPENGER N., The Realization of Monotone Boolean Functions, A.C.M. Sym. on Theory of Comp., 1976, pp. 204-211.4346540366.94050","DOI":"10.1145\/800113.803650"},{"key":"R14","unstructured":"14. ROGERS H. Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, NY, 1967.2244620183.01401"},{"key":"R15","unstructured":"15. SAVAGE J., The Complexity of Computing, 1976, Wiley and Sons, NY.4952050391.68025"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"16. SCHNORR C. P., The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Infor., Vol. 7, 1976, pp. 95-107.4218890338.02019","DOI":"10.1007\/BF00265223"},{"key":"R17","unstructured":"17. SHOLOMOV L. A., Information Complexity Problems of Minimal Realization of Boolean Functions by Combinational Schemas, Prob. of Cybernetics, Vol. 26, 1973, pp. 207-256."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"18. TRACHTENBROT B. A., On Problems Solvable by Successive Trials, Math. Found. of Comp. Sc., 1975 (Lect. Notes in Comp. Science n\u00b0 32, Springer-Verlag, pp. 125-137).3953290357.68060","DOI":"10.1007\/3-540-07389-2_187"},{"key":"R19","unstructured":"19. YABLONSKI S. V., On Algorithmic Difficulties in Synthesis of Minimal Schemas, Prob. of Cybernetics, Vol. 2, 1959, pp. 75-121.129088"}],"container-title":["RAIRO. Informatique th\u00e9orique"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1979130100871\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,1]],"date-time":"2020-10-01T22:58:24Z","timestamp":1601593104000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1979130100871"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979]]},"references-count":19,"journal-issue":{"issue":"1"},"alternative-id":["ita1979130100871"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1979130100871","relation":{},"ISSN":["0399-0540"],"issn-type":[{"value":"0399-0540","type":"print"}],"subject":[],"published":{"date-parts":[[1979]]}}}