Statman, R. Complexity of derivations from quantifier-free Horn formulae, mechanical introduction of explicit definitions, and refinement of completeness theorems. (English) Zbl 0441.03021 Logic colloquium 76, Proc. Conf., Oxford 1976, Stud. Logic Found. Math., Vol. 87, 505-518 (1977). MSC: 03F20 03D15 PDFBibTeX XML
Berg, Eugen Peter; Lischke, Gerhard Zwei Sätze für schwache Erhaltungsmasse. (German) Zbl 0439.03016 Z. Math. Logik Grundlagen Math. 23, 409-410 (1977). MSC: 03D15 03D20 PDFBibTeX XMLCite \textit{E. P. Berg} and \textit{G. Lischke}, Z. Math. Logik Grundlagen Math. 23, 409--410 (1977; Zbl 0439.03016) Full Text: DOI
Fleischmann, Klaus; Mahr, Bernd; Siefkes, Dirk Bounded concatenation theory as a uniform method for proving lower complexity bounds. (English) Zbl 0439.03004 Logic colloquium 76, Proc. Conf., Oxford 1976, Stud. Logic Found. Math., Vol. 87, 471-490 (1977). MSC: 03B25 03D15 PDFBibTeX XML
Verbeek, R.; Weihrauch, K. Data presentation and computational complexity. (English) Zbl 0426.03040 Proc. Conf. theoretical computer science, Waterloo/Ontario 1977, 111-119 (1977). MSC: 03D15 03D05 03D60 68P05 68Q25 PDFBibTeX XML
Bennison, Victor L. On the problem of determining measure-independence. (English) Zbl 0415.03028 Proc. Conf. theoretical computer science, Waterloo/Ontario 1977, 100-110 (1977). MSC: 03D15 03D25 03D35 PDFBibTeX XML
Lewis, Harry R. A measure of complexity for combinatorial decision problems of the tiling variety. (English) Zbl 0414.03008 Proc. Conf. theoretical computer science, Waterloo/Ontario 1977, 94-99 (1977). MSC: 03B25 03D15 03D10 03D60 68Q45 PDFBibTeX XML
Freidzon, R. I. Table approximations to recursive predicates. (English) Zbl 0404.03029 J. Sov. Math. 8, 337-341 (1977). MSC: 03D20 03D15 PDFBibTeX XMLCite \textit{R. I. Freidzon}, J. Sov. Math. 8, 337--341 (1977; Zbl 0404.03029) Full Text: DOI
Lovász, László; Gacs, P. Some remarks on generalized spectra. (English) Zbl 0398.03025 Z. Math. Logik Grundlagen Math. 23, 547-554 (1977). MSC: 03D15 03B15 PDFBibTeX XMLCite \textit{L. Lovász} and \textit{P. Gacs}, Z. Math. Logik Grundlagen Math. 23, 547--554 (1977; Zbl 0398.03025) Full Text: DOI
Simon, Janos Polynomially bounded quantification over higher types and a new hierarchy of the elementary sets. (English) Zbl 0393.03028 Non-classical Logic, Model Theory Comput., Proc. 3rd Lat.-Am. Symp. math. Logic, Campinas 1976, Stud. Logic Found. Math. 89, 267-281 (1977). Reviewer: P. Odifreddi (Torino) MSC: 03D10 03D15 PDFBibTeX XML
Bremer, H. Ein vollständiges Problem auf der Baummaschine. (German) Zbl 0392.68053 Theor. Comput. Sci., 3rd GI Conf., Darmstadt 1977, Lect. Notes Comput. Sci. 48, 391-406 (1977). MSC: 68Q45 03D05 03D10 03G05 03D15 68Q05 PDFBibTeX XML
Trakhtenbrot, B. A. Frequency algorithms and computations. (English) Zbl 0392.68030 Math. Found. Comput. Sci., Proc. 6th Symp., Tatranska Lomnica 1977, Lect. Notes Comput. Sci. 53, 148-161 (1977). MSC: 68W99 68Q25 03D60 03D15 PDFBibTeX XML
Katerinockina, N. N. Search for a maximal upper zero for a class of monotone functions in k- valued logic. (English. Russian original) Zbl 0392.03027 Sov. Math., Dokl. 18, 751-754 (1977); translation from Dokl. Akad. Nauk SSSR 234, 746-749 (1977). MSC: 03D15 03B50 03G05 PDFBibTeX XMLCite \textit{N. N. Katerinockina}, Sov. Math., Dokl. 18, 751--754 (1977; Zbl 0392.03027); translation from Dokl. Akad. Nauk SSSR 234, 746--749 (1977)
Sakuov, S. N. Fast Turing computations and their linear speedup. (English. Russian original) Zbl 0391.68026 Sov. Math., Dokl. 18(1977), 1250-1252 (1978); translation from Dokl. Akad. Nauk SSSR 236, 556-557 (1977). MSC: 68Q25 03D15 68Q05 PDFBibTeX XMLCite \textit{S. N. Sakuov}, Sov. Math., Dokl. 18, 1250--1252 (1977; Zbl 0391.68026); translation from Dokl. Akad. Nauk SSSR 236, 556--557 (1977)
Vinogradov, A. P. On the existence of a majorizing local algorithm in effectively describable problems of computing information. (English. Russian original) Zbl 0386.03021 Sov. Math., Dokl. 18(1977), 1014-1018 (1978); translation from Dokl. Akad. Nauk SSSR 235, 745-748 (1977). MSC: 03D15 03F99 68W99 PDFBibTeX XMLCite \textit{A. P. Vinogradov}, Sov. Math., Dokl. 18, 1014--1018 (1977; Zbl 0386.03021); translation from Dokl. Akad. Nauk SSSR 235, 745--748 (1977)
Jacobs, Barry E. On generalized computational complexity. (English) Zbl 0384.03022 J. Symb. Log. 42, 47-58 (1977). MSC: 03D15 03D60 PDFBibTeX XMLCite \textit{B. E. Jacobs}, J. Symb. Log. 42, 47--58 (1977; Zbl 0384.03022) Full Text: DOI
Kanovic, M. I. On the precision of a complexity criterion for nonrecursiveness and universality. (English. Russian original) Zbl 0383.03029 Sov. Math., Dokl. 18, 232-236 (1977); translation from Dokl. Akad. Nauk SSSR 232, 1249-1252 (1977). MSC: 03D30 03D20 03D25 03D15 PDFBibTeX XMLCite \textit{M. I. Kanovic}, Sov. Math., Dokl. 18, 232--236 (1977; Zbl 0383.03029); translation from Dokl. Akad. Nauk SSSR 232, 1249--1252 (1977)
Mokazjan, A. A. Some properties of relativizated Kolmogorov complexities. (Russian) Zbl 0383.03026 Dokl. Akad. Nauk Arm. SSR 64, 2, 77-80 (1977). MSC: 03D15 03D20 03D25 PDFBibTeX XMLCite \textit{A. A. Mokazjan}, Dokl., Akad. Nauk Arm. SSR 64, 2, 77--80 (1977; Zbl 0383.03026)
Levin, L. A. On a concrete method of assigning complexity measures. (English. Russian original) Zbl 0382.03044 Sov. Math., Dokl. 18, 727-731 (1977); translation from Dokl. Akad. Nauk SSSR 234, 536-539 (1977). MSC: 03F60 03F65 94A15 03D15 68W99 68Q25 PDFBibTeX XMLCite \textit{L. A. Levin}, Sov. Math., Dokl. 18, 727--731 (1977; Zbl 0382.03044); translation from Dokl. Akad. Nauk SSSR 234, 536--539 (1977)
Engeler, Erwin Structural relations between programs and problems. (English) Zbl 0381.03027 Logic, Found. Math., Comput. Theory; Proc. 5th int. Congr., London/Ontario 1975, Part 1, 267-280 (1977). MSC: 03D15 16W20 PDFBibTeX XML