Asveld, Peter R. J. Complete symmetry in D2L systems and cellular automata. (English) Zbl 0655.68066 Int. J. Comput. Math. 19, No. 3-4, 211-223 (1986). MSC: 68Q80 68Q42 68Q05 68Q45 68Q25 PDFBibTeX XMLCite \textit{P. R. J. Asveld}, Int. J. Comput. Math. 19, No. 3--4, 211--223 (1986; Zbl 0655.68066) Full Text: DOI Link
Hartmanis, Juris; Hemachandra, Lane Complexity classes without machines: on complete languages for UP. (English) Zbl 0655.68043 Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 123-135 (1986). MSC: 68Q25 03D05 03D15 68Q05 PDFBibTeX XML
Hartmanis, Juris; Li, Ming; Yesha, Yaacov Containment, separation, complete sets, and immunity of complexity classes. (English) Zbl 0654.68051 Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 136-145 (1986). MSC: 68Q25 03D15 PDFBibTeX XML
Börger, Egon Rödding, Dieter (ed.) Berechenbarkeit, Komplexität, Logik. Eine Einführung in Algorithmen, Sprachen und Kalküle unter besonderer Berücksichtigung ihrer Komplexität. Hrsg. von Dieter Rödding. 2., ber. Aufl. (German) Zbl 0649.03028 Braunschweig-Wiesbaden: Friedr. Vieweg & Sohn. XVII, 469 S.; DM 64.00 (1986). MSC: 03Dxx 03-01 03-02 03D15 03B10 68W99 03D05 03F05 03D55 03D20 03D30 03D35 68Q45 PDFBibTeX XML
Alberts, M. Ya. Possibilities of various types of alternating automata. (English. Russian original) Zbl 0644.68057 Cybernetics 22, No. 6, 714-720 (1986); translation from Kibernetika 1986, No. 6, 26-30 (1986). MSC: 68Q25 68Q45 68Q05 03D05 03D10 PDFBibTeX XMLCite \textit{M. Ya. Alberts}, Cybernetics 22, No. 6, 714--720 (1986; Zbl 0644.68057); translation from Kibernetika 1986, No. 6, 26--30 (1986) Full Text: DOI
Rovan, Branislav Complexity classes of g-systems are AFL. (English) Zbl 0639.68064 Acta Math. Univ. Comenianae 48-49, 283-297 (1986). MSC: 68Q45 68Q25 PDFBibTeX XMLCite \textit{B. Rovan}, Acta Math. Univ. Comenianae 48--49, 283--297 (1986; Zbl 0639.68064)
Dymond, Patrick W. On nondeterminism in parallel computation. (English) Zbl 0638.68032 Theor. Comput. Sci. 47, 111-120 (1986). MSC: 68Q25 68Q05 68Q45 PDFBibTeX XMLCite \textit{P. W. Dymond}, Theor. Comput. Sci. 47, 111--120 (1986; Zbl 0638.68032) Full Text: DOI
Félix, Y.; Thomas, J. C. On the ubiquity of the rational homotopy Lie algebra of a topological space. (English) Zbl 0637.55005 Bull. Soc. Math. Belg., Sér. A 38, 175-190 (1986). Reviewer: St.Papadima MSC: 55P62 55M30 55Q05 55Q99 PDFBibTeX XMLCite \textit{Y. Félix} and \textit{J. C. Thomas}, Bull. Soc. Math. Belg., Sér. A 38, 175--190 (1986; Zbl 0637.55005)
Paris, J. B.; Handley, W. G.; Wilkie, A. J. Characterizing some low arithmetic classes. (English) Zbl 0635.03033 Theory of algorithms, Colloq. Pécs/Hung. 1984, Colloq. Math. Soc. János Bolyai 44, 353-364 (1986). Reviewer: D.Yu.Grigor’ev MSC: 03D15 68Q25 PDFBibTeX XML
Zachos, Stathis Probabilistic quantifiers, adversaries, and complexity classes: An overview. (English) Zbl 0632.03035 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 383-400 (1986). Reviewer: D.Mundici MSC: 03D15 68Q25 68Q05 PDFBibTeX XML
Hemmerling, A. On the power of cellular parallelism. (English) Zbl 0631.68046 Parallel processing by cellular automata and arrays, Proc. 3rd Int. Workshop, Berlin/GDR 1986, Math. Res. 29, 210-217 (1986). MSC: 68Q25 68Q05 68Q80 PDFBibTeX XML
Denenberg, Larry; Gurevich, Yuri; Shelah, Saharon Definability by constant-depth polynomial-size circuits. (English) Zbl 0629.94023 Inf. Control 70, 216-240 (1986). Reviewer: A. Leitsch (Wien) MSC: 94C11 68Q25 03C40 03C52 03D15 PDFBibTeX XMLCite \textit{L. Denenberg} et al., Inf. Control 70, 216--240 (1986; Zbl 0629.94023) Full Text: DOI
Karpinski, Marek; Verbeek, Rutger On the power of two-way random generators and the impossibility of deterministic poly-space simulation. (English) Zbl 0629.68046 Inf. Control 71, 131-142 (1986). MSC: 68Q25 PDFBibTeX XMLCite \textit{M. Karpinski} and \textit{R. Verbeek}, Inf. Control 71, 131--142 (1986; Zbl 0629.68046) Full Text: DOI
Heller, Hans On relativized exponential and probabilistic complexity classes. (English) Zbl 0628.68047 Inf. Control 71, 231-243 (1986). Reviewer: D.Yu.Grigoryev MSC: 68Q25 03D15 PDFBibTeX XMLCite \textit{H. Heller}, Inf. Control 71, 231--243 (1986; Zbl 0628.68047) Full Text: DOI
Gundermann, Thomas; Wechsung, Gerd Nondeterministic Turing machines with modified acceptance. (English) Zbl 0628.03026 Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 396-404 (1986). Reviewer: E.Heinrich MSC: 03D15 03D10 68Q05 68Q25 PDFBibTeX XML
Butler, Gregory Data structures and algorithms for cyclically extended Schreier vectors. (English) Zbl 0627.20001 Numerical mathematics and computing, Proc. 15th Conf., Winnipeg/Manitoba 1985, Congr. Numerantium 52, 63-78 (1986). Reviewer: J.Neubüser MSC: 20-04 20D10 20B05 20F05 20F16 20D30 PDFBibTeX XML
Culik, K. II; Gruska, J.; Salomaa, A. Systolic trellis automata: Stability, decidability and complexity. (English) Zbl 0626.68048 Inf. Control 71, 218-230 (1986). Reviewer: G.Wechsung MSC: 68Q45 68Q25 68Q80 PDFBibTeX XMLCite \textit{K. Culik II} et al., Inf. Control 71, 218--230 (1986; Zbl 0626.68048) Full Text: DOI
Štěpánek, Petr; Štěpánková, Olga Logic programs and alternation. (English) Zbl 0626.68041 Logic programming, Proc. 3rd Int. Conf., London 1986, Lect. Notes Comput. Sci. 225, 99-106 (1986). Reviewer: E.Heinrich MSC: 68Q05 68Q25 68N01 PDFBibTeX XML
Balcázar, Jose L.; Book, Ronald V.; Schöning, Uwe The polynomial-time hierarchy and sparse oracles. (English) Zbl 0625.68033 J. Assoc. Comput. Mach. 33, No. 3, 603-617 (1986). MSC: 68Q25 PDFBibTeX XMLCite \textit{J. L. Balcázar} et al., J. Assoc. Comput. Mach. 33, 603--617 (1986; Zbl 0625.68033) Full Text: DOI
Regan, Kenneth W. The topology of provability in complexity theory. (English) Zbl 0624.03033 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 291-310 (1986). Reviewer: D.Mundici MSC: 03D15 03D30 68Q25 PDFBibTeX XML
Moriya, Etsuro; Iwata, Shigeki; Kasai, Takumi A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic Turing machines. (English) Zbl 0623.68051 Inf. Control 70, 179-185 (1986). MSC: 68Q25 68Q05 PDFBibTeX XMLCite \textit{E. Moriya} et al., Inf. Control 70, 179--185 (1986; Zbl 0623.68051) Full Text: DOI
Wagner, Klaus W. The complexity of combinatorial problems with succinct input representation. (English) Zbl 0621.68032 Acta Inf. 23, 325-356 (1986). Reviewer: D.Yu.Grigoryev MSC: 68Q25 03D15 PDFBibTeX XMLCite \textit{K. W. Wagner}, Acta Inf. 23, 325--356 (1986; Zbl 0621.68032) Full Text: DOI
Ko, Ker-I; Orponen, Pekka; Schöning, Uwe; Watanabe, Osamu What is a hard instance of a computational problem? (English) Zbl 0617.68048 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 197-217 (1986). Reviewer: H.Alt MSC: 68Q25 03D15 PDFBibTeX XML
Zachos, Stathis; Heller, Hans A decisive characterization of BPP. (English) Zbl 0616.68049 Inf. Control 69, 125-135 (1986). MSC: 68Q25 03D15 03D10 68W99 68Q05 94A60 PDFBibTeX XMLCite \textit{S. Zachos} and \textit{H. Heller}, Inf. Control 69, 125--135 (1986; Zbl 0616.68049) Full Text: DOI
von zur Gathen, Joachim Parallel arithmetic computations: A survey. (English) Zbl 0616.68037 Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 93-112 (1986). MSC: 68W30 68Q25 68N25 68-02 PDFBibTeX XML
Liśkiewicz, M.; Loryś, K.; Piotrow, M. The characterization of some complexity classes by recursion schemata. (English) Zbl 0615.03025 Theory of algorithms, Colloq. Pécs/Hung. 1984, Colloq. Math. Soc. János Bolyai 44, 313-322 (1986). Reviewer: S.P.Yukna MSC: 03D15 03D20 68Q25 PDFBibTeX XML
Lindsay, Peter A. Alternation and \(\omega\)-type Turing acceptors. (English) Zbl 0612.68074 Theor. Comput. Sci. 43, 107-115 (1986). Reviewer: U.Klemm MSC: 68Q45 68Q05 68Q25 PDFBibTeX XMLCite \textit{P. A. Lindsay}, Theor. Comput. Sci. 43, 107--115 (1986; Zbl 0612.68074) Full Text: DOI
Boppana, R. B.; Lagarias, J. C. One-way functions and circuit complexity. (English) Zbl 0612.68036 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 51-65 (1986). MSC: 68Q25 94C10 94A60 PDFBibTeX XML
Orponen, Pekka; Schöning, Uwe The density and complexity of polynomial cores for intractable sets. (English) Zbl 0611.68021 Inf. Control 70, 54-68 (1986). MSC: 68Q25 68Q05 PDFBibTeX XMLCite \textit{P. Orponen} and \textit{U. Schöning}, Inf. Control 70, 54--68 (1986; Zbl 0611.68021) Full Text: DOI
Torenvliet, Leen; van Emde Boas, Peter Diagonalisation methods in a polynomial setting. (English) Zbl 0611.68019 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 330-346 (1986). MSC: 68Q25 PDFBibTeX XML
Chai, Jinyi; Hemachandra, Lane The Boolean hierarchy: Hardware over NP. (English) Zbl 0611.68018 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 105-124 (1986). MSC: 68Q25 PDFBibTeX XML
Meinel, Christoph p-projection reducibility and the complexity classes \({\mathcal L}\) nonuniform and \({\mathcal N}{\mathcal L}\) (nonuniform). (English) Zbl 0611.03021 Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 527-535 (1986). Reviewer: A.Brandstädt MSC: 03D15 68Q25 PDFBibTeX XML
Geske, John; Grollmann, Joachim Relativizations of unambiguous and random polynomial time classes. (English) Zbl 0609.68038 SIAM J. Comput. 15, 511-519 (1986). MSC: 68Q25 68Q05 03D15 03D10 94A60 PDFBibTeX XMLCite \textit{J. Geske} and \textit{J. Grollmann}, SIAM J. Comput. 15, 511--519 (1986; Zbl 0609.68038) Full Text: DOI
Balcázar, José L. On \(\Delta ^ P_ 2\)-immunity. (English) Zbl 0609.68036 Inf. Process. Lett. 23, 25-28 (1986). MSC: 68Q25 03D15 PDFBibTeX XMLCite \textit{J. L. Balcázar}, Inf. Process. Lett. 23, 25--28 (1986; Zbl 0609.68036) Full Text: DOI
Hartmanis, Juris; Hemachandra, Lane On sparse oracles separating feasible complexity classes. (English) Zbl 0605.68034 Theoretical aspects of computer science, 3rd Annu. Symp., Orsay/France 1986, Lect. Notes Comput. Sci. 210, 321-333 (1986). MSC: 68Q25 PDFBibTeX XML
Lange, Klaus-Jörn Decompositions of nondeterministic reductions. (English) Zbl 0596.68043 Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 206-214 (1986). MSC: 68Q25 03D15 03D30 PDFBibTeX XML
Lischke, Gerhard Oracle-constructions to prove all possible relationships between relativizations of P, NP, EL, NEL, EP and NEP. (English) Zbl 0594.68045 Z. Math. Logik Grundlagen Math. 32, 257-270 (1986). MSC: 68Q25 03D15 PDFBibTeX XMLCite \textit{G. Lischke}, Z. Math. Logik Grundlagen Math. 32, 257--270 (1986; Zbl 0594.68045) Full Text: DOI
Wagner, K.; Wechsung, G. Computational complexity. (English) Zbl 0584.68062 Mathematiche Monographien, Bd. 19. Berlin: VEB Deutscher Verlag der Wissenschaften, 551 p. (1986). Reviewer: M.Kratko MSC: 68Q25 03D15 68-02 03-02 68-01 03-01 PDFBibTeX XML
Wagner, K.; Wechsung, G. Computational complexity. (English) Zbl 0584.68061 Mathematics and its Applications (East European Series), 21. Dordrecht etc.: D. Reidel Publishing Company, a member of the Kluwer Academic Publishers Group (orig. publ. by VEB Deutscher Verlag der Wissenschaften, Berlin). 551 p. Dfl 205.00; $ 79.00; £56.95 (1986). MSC: 68Q25 03D15 68-02 03-02 68-01 03-01 PDFBibTeX XML
Lischke, Gerhard Oracle-constructions to prove all possible relationships between relativizations of P, NP, EL, NEL, EP and NEP. (English) Zbl 0578.68038 Z. Math. Logik Grundlagen Math. (to appear). MSC: 68Q25 03D15 PDFBibTeX XML