Leivant, Daniel M. Alternating Turing machines for inductive languages. (English) Zbl 1322.03030 Log. Methods Comput. Sci. 9, No. 3, Paper No. 31, 12 p. (2013). Reviewer: Stela K. Nikolova (Sofia) MSC: 03D10 03D60 03D70 PDF BibTeX XML Cite \textit{D. M. Leivant}, Log. Methods Comput. Sci. 9, No. 3, Paper No. 31, 12 p. (2013; Zbl 1322.03030) Full Text: DOI
Kozik, Marcin A 2EXPTIME complete varietal membership problem. (English) Zbl 1192.68369 SIAM J. Comput. 38, No. 6, 2443-2467 (2009). MSC: 68Q25 08B15 08A40 68Q65 PDF BibTeX XML Cite \textit{M. Kozik}, SIAM J. Comput. 38, No. 6, 2443--2467 (2009; Zbl 1192.68369) Full Text: DOI
Kuśmierek, Dariusz The inhabitation problem for rank two intersection types. (English) Zbl 1215.03025 Ronchi della Rocca, Simona (ed.), Typed lambda calculi and applications. 8th international conference, TLCA 2007, Paris, France, June 26–28, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73227-3/pbk). Lecture Notes in Computer Science 4583, 240-254 (2007). MSC: 03B40 03D10 68Q17 PDF BibTeX XML Cite \textit{D. Kuśmierek}, Lect. Notes Comput. Sci. 4583, 240--254 (2007; Zbl 1215.03025) Full Text: DOI
Sosík, Petr; Rodríguez-Patón, Alfonso Membrane computing and complexity theory: A characterization of PSPACE. (English) Zbl 1178.68260 J. Comput. Syst. Sci. 73, No. 1, 137-152 (2007). MSC: 68Q05 68Q10 PDF BibTeX XML Cite \textit{P. Sosík} and \textit{A. Rodríguez-Patón}, J. Comput. Syst. Sci. 73, No. 1, 137--152 (2007; Zbl 1178.68260) Full Text: DOI
Szepietowski, Andrzej A note on alternating one-pebble Turing machines with sublogarithmic space. (English) Zbl 1185.68332 Inf. Process. Lett. 98, No. 5, 174-176 (2006). MSC: 68Q05 68Q25 PDF BibTeX XML Cite \textit{A. Szepietowski}, Inf. Process. Lett. 98, No. 5, 174--176 (2006; Zbl 1185.68332) Full Text: DOI
Okazaki, Tokio; Inoue, Atsuyuki; Inoue, Katsushi; Ito, Akira; Wang, Yue Non-closure property of space-bounded two-dimensional alternating Turing machines. (English) Zbl 1018.68028 Inf. Sci. 146, No. 1-4, 151-170 (2002). MSC: 68Q05 PDF BibTeX XML Cite \textit{T. Okazaki} et al., Inf. Sci. 146, No. 1--4, 151--170 (2002; Zbl 1018.68028) Full Text: DOI
Bergman, Clifford; Juedes, David; Slutzki, Giora Computational complexity of term-equivalence. (English) Zbl 0931.68058 Int. J. Algebra Comput. 9, No. 1, 113-128 (1999). Reviewer: Clifford Bergman (Ames) MSC: 68Q15 08A40 PDF BibTeX XML Full Text: DOI
Cai, Liming; Chen, Jianer; Håstad, Johan Circuit bottom fan-in and computational power. (English) Zbl 0907.68077 SIAM J. Comput. 27, No. 2, 341-355 (1998). MSC: 68Q05 68Q15 68Q25 68Q30 68Q10 PDF BibTeX XML Cite \textit{L. Cai} et al., SIAM J. Comput. 27, No. 2, 341--355 (1998; Zbl 0907.68077) Full Text: DOI
Szwast, Wiesław The class of existential second-order Bernays-Schönfinkel sentences and the exponential hierarchy. (English) Zbl 0870.03016 Zesz. Nauk. Uniw. Opol., Mat. 29, 189-197 (1995). MSC: 03D15 03D10 68Q15 PDF BibTeX XML Cite \textit{W. Szwast}, Zesz. Nauk. Uniw. Opol., Mat. 29, 189--197 (1995; Zbl 0870.03016)
Inoue, Katsushi; Ito, Akira; Takanami, Itsuo On 1-inkdot alternating Turing machines with small space. (English) Zbl 0805.68039 Theor. Comput. Sci. 127, No. 1, 171-179 (1994). MSC: 68Q05 68Q15 PDF BibTeX XML Cite \textit{K. Inoue} et al., Theor. Comput. Sci. 127, No. 1, 171--179 (1994; Zbl 0805.68039) Full Text: DOI
Trahan, Jerry L.; Ramachandran, Vijaya; Loui, Michael C. Parallel random access machines with both multiplication and shifts. (English) Zbl 0804.68051 Inf. Comput. 110, No. 1, 96-118 (1994). MSC: 68Q15 03D15 68Q10 68Q05 PDF BibTeX XML Cite \textit{J. L. Trahan} et al., Inf. Comput. 110, No. 1, 96--118 (1994; Zbl 0804.68051) Full Text: DOI
Geffert, V. Sublogarithmic \(\Sigma_ 2\)-space is not closed under complement and other separation results. (English) Zbl 0804.68047 RAIRO, Inform. Théor. Appl. 27, No. 4, 349-366 (1993). Reviewer: W.Nico (Hayward) MSC: 68Q15 03D15 68Q05 PDF BibTeX XML Cite \textit{V. Geffert}, RAIRO, Inform. Théor. Appl. 27, No. 4, 349--366 (1993; Zbl 0804.68047) Full Text: DOI EuDML
Cook, Stephen A.; Dymond, Patrick W. Parallel pointer machines. (English) Zbl 0781.68052 Comput. Complexity 3, No. 1, 19-30 (1993). Reviewer: P.van Emde Boas (Amsterdam) MSC: 68Q05 68Q10 68Q80 PDF BibTeX XML Cite \textit{S. A. Cook} and \textit{P. W. Dymond}, Comput. Complexity 3, No. 1, 19--30 (1993; Zbl 0781.68052) Full Text: DOI
Inoue, Katsushi; Ito, Akira; Takanami, Itsuo Alternating Turing machines with modified accepting structure. (English) Zbl 0792.68038 Int. J. Found. Comput. Sci. 2, No. 4, 401-417 (1991). MSC: 68Q05 68Q15 03D10 PDF BibTeX XML Cite \textit{K. Inoue} et al., Int. J. Found. Comput. Sci. 2, No. 4, 401--417 (1991; Zbl 0792.68038) Full Text: DOI
Jiang, Tao On the complexity of (off-line) 1-tape ATM’s running in constant reversals. (English) Zbl 0767.68040 Advances in computing and information, ICCI ’90, Proc. Int. Conf., Niagara Falls/Canada 1990, Lect. Notes Comput. Sci. 468, 92-99 (1991). MSC: 68Q05 68Q15 03D10 03D15 03D25 PDF BibTeX XML Cite \textit{T. Jiang}, Lect. Notes Comput. Sci. 468, 92--99 (1991; Zbl 0767.68040)
Allender, Eric W. P-uniform circuit complexity. (English) Zbl 0697.68031 J. Assoc. Comput. Mach. 36, No. 4, 912-928 (1989). MSC: 68Q25 03D15 68Q05 PDF BibTeX XML Cite \textit{E. W. Allender}, J. Assoc. Comput. Mach. 36, No. 4, 912--928 (1989; Zbl 0697.68031) Full Text: DOI
Ladner, Richard E. Polynomial space counting problems. (English) Zbl 0692.68036 SIAM J. Comput. 18, No. 6, 1087-1097 (1989). MSC: 68Q25 03D15 68Q05 03D10 PDF BibTeX XML Cite \textit{R. E. Ladner}, SIAM J. Comput. 18, No. 6, 1087--1097 (1989; Zbl 0692.68036) Full Text: DOI
Szepietowski, Andrzej Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space. (English) Zbl 0684.68062 Inf. Process. Lett. 33, No. 2, 73-78 (1989). MSC: 68Q25 68Q05 03D15 PDF BibTeX XML Cite \textit{A. Szepietowski}, Inf. Process. Lett. 33, No. 2, 73--78 (1989; Zbl 0684.68062) Full Text: DOI
Dill, Jens M. A counterexample for “A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars”. (English) Zbl 0667.68081 J. Assoc. Comput. Mach. 36, No. 1, 92-96 (1989). MSC: 68Q45 68Q25 68N25 PDF BibTeX XML Cite \textit{J. M. Dill}, J. Assoc. Comput. Mach. 36, No. 1, 92--96 (1989; Zbl 0667.68081) Full Text: DOI
Hromkovič, Juraj Tradeoffs for language recognition on alternating machines. (English) Zbl 0667.68060 Theor. Comput. Sci. 63, No. 2, 203-221 (1989). Reviewer: M.Clausen MSC: 68Q25 68Q05 03D15 PDF BibTeX XML Cite \textit{J. Hromkovič}, Theor. Comput. Sci. 63, No. 2, 203--221 (1989; Zbl 0667.68060) Full Text: DOI
King, K. N. Alternating multihead finite automata. (English) Zbl 0665.68064 Theor. Comput. Sci. 61, No. 2-3, 149-174 (1988). MSC: 68Q45 68Q25 03D05 68Q05 PDF BibTeX XML Cite \textit{K. N. King}, Theor. Comput. Sci. 61, No. 2--3, 149--174 (1988; Zbl 0665.68064) Full Text: DOI
Ibarra, Oscar H.; Jiang, Tao; Ravikumar, Bala; Chang, Jik H. On some languages in \(NC^ 1\). (English) Zbl 0661.68042 VLSI algorithms and architectures, Proc. 3rd Aegean Workshop Comput., Corfu/Greece 1988, Lect. Notes Comput. Sci. 319, 64-73 (1988). Reviewer: D.Yu.Grigor’ev MSC: 68Q25 68Q45 PDF BibTeX XML
Ibarra, Oscar H.; Jiang, Tao; Ravikumar, Bala Some subclasses of context-free languages in \(NC^ 1\). (English) Zbl 0659.68073 Inf. Process. Lett. 29, No. 3, 111-117 (1988). Reviewer: J.Hromkovič MSC: 68Q25 68Q05 68Q45 PDF BibTeX XML Cite \textit{O. H. Ibarra} et al., Inf. Process. Lett. 29, No. 3, 111--117 (1988; Zbl 0659.68073) Full Text: DOI
Liśkiewicz, Maciej; Loryś, Krzysztof Alternating real-time computations. (English) Zbl 0658.68056 Inf. Process. Lett. 28, No. 6, 311-316 (1988). MSC: 68Q05 68Q25 68Q45 PDF BibTeX XML Cite \textit{M. Liśkiewicz} and \textit{K. Loryś}, Inf. Process. Lett. 28, No. 6, 311--316 (1988; Zbl 0658.68056) Full Text: DOI
Parberry, Ian; Schnitger, Georg Parallel computation with threshold functions. (English) Zbl 0652.68064 J. Comput. Syst. Sci. 36, No. 3, 278-302 (1988). MSC: 68Q05 68Q25 PDF BibTeX XML Cite \textit{I. Parberry} and \textit{G. Schnitger}, J. Comput. Syst. Sci. 36, No. 3, 278--302 (1988; Zbl 0652.68064) Full Text: DOI
Piotrów, Marek On complexity of counting. (English) Zbl 0652.68057 Mathematical foundations of computer science 1988, Proc. 13th Symp., Carlsbad/Czech. 1988, Lect. Notes Comput. Sci. 324, 472-482 (1988). MSC: 68Q25 68Q05 PDF BibTeX XML
Ibarra, Oscar H.; Jiang, Tao On one-way cellular arrays. (English) Zbl 0646.68070 SIAM J. Comput. 16, 1135-1154 (1987). MSC: 68Q80 68Q25 68Q45 PDF BibTeX XML Cite \textit{O. H. Ibarra} and \textit{T. Jiang}, SIAM J. Comput. 16, 1135--1154 (1987; Zbl 0646.68070) Full Text: DOI
Yamamoto, Hiroaki; Noguchi, Shoichi Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs. (English) Zbl 0631.68051 Inf. Comput. 75, 144-161 (1987). Reviewer: M.Kratko MSC: 68Q05 68Q25 68Q45 03D10 PDF BibTeX XML Cite \textit{H. Yamamoto} and \textit{S. Noguchi}, Inf. Comput. 75, 144--161 (1987; Zbl 0631.68051) Full Text: DOI
Maass, Wolfgang; Schorr, Amir Speed-up of Turing machines with one work tape and a two-way input tape. (English) Zbl 0631.68050 SIAM J. Comput. 16, 195-202 (1987). Reviewer: M.Kratko MSC: 68Q05 68Q25 03D10 03D15 PDF BibTeX XML Cite \textit{W. Maass} and \textit{A. Schorr}, SIAM J. Comput. 16, 195--202 (1987; Zbl 0631.68050) Full Text: DOI
Woods, Alan Bounded arithmetic formulas and Turing machines of constant alternation. (English) Zbl 0615.03022 Logic colloq. ’84, Proc. Colloq., Manchester/U.K. 1984, Stud. Logic Found. Math. 120, 355-377 (1986). Reviewer: D.Mundici MSC: 03D10 03D15 03F30 PDF BibTeX XML
Parberry, Ian; Schnitger, Georg Parallel computation with threshold functions. (English) Zbl 0611.68024 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 272-290 (1986). MSC: 68Q05 68Q25 68N25 94C10 PDF BibTeX XML
Hromkovič, Juraj Tradeoffs for language recognition on parallel computing models. (English) Zbl 0594.68046 Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 157-166 (1986). MSC: 68Q25 68Q05 68Q45 PDF BibTeX XML
Manber, Udi; Tompa, Martin The complexity of problems on probabilistic, nondeterministic, and alternating decision trees. (English) Zbl 0631.68044 J. Assoc. Comput. Mach. 32, 720-732 (1985). MSC: 68Q25 68W99 PDF BibTeX XML Cite \textit{U. Manber} and \textit{M. Tompa}, J. Assoc. Comput. Mach. 32, 720--732 (1985; Zbl 0631.68044) Full Text: DOI
Wechsung, Gerd On the Boolean closure of NP. (English) Zbl 0581.68043 Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 485-493 (1985). Reviewer: A.Slisenko MSC: 68Q25 03D15 03D10 68Q05 03D20 PDF BibTeX XML
Shapiro, Ehud Y. Alternation and the computational complexity of logic programs. (English) Zbl 0579.68030 J. Logic Program. 1, 19-33 (1984). Reviewer: D.Lucanu MSC: 68Q25 68Q05 PDF BibTeX XML Cite \textit{E. Y. Shapiro}, J. Log. Program. 1, 19--33 (1984; Zbl 0579.68030) Full Text: DOI
Inoue, Katsushi; Takanami, Itsuo; Taniguchi, Hiroshi Two-dimensional alternative Turing machines. (English) Zbl 0539.68039 Theor. Comput. Sci. 27, 61-83 (1983). Reviewer: M.Kratko MSC: 68Q05 68Q25 PDF BibTeX XML Cite \textit{K. Inoue} et al., Theor. Comput. Sci. 27, 61--83 (1983; Zbl 0539.68039) Full Text: DOI
Volger, Hugo Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories. (English) Zbl 0538.03035 Theor. Comput. Sci. 23, 333-337 (1983). Reviewer: J.M.Plotkin MSC: 03D10 03B25 PDF BibTeX XML Cite \textit{H. Volger}, Theor. Comput. Sci. 23, 333--337 (1983; Zbl 0538.03035) Full Text: DOI
Chlebus, Bogdan S. On four logics of programs and complexity of their satisfiability problems: extended abstract. (English) Zbl 0513.68023 Logics of programs and their applications, Proc. Symp., Poznan 1980, Lect. Notes Comput. Sci. 148, 98-107 (1983). MSC: 68Q65 68N01 03B60 03B45 03D15 PDF BibTeX XML
Chlebus, Bogdan S. On the computational complexity of satisfiability in propositional logics of programs. (English) Zbl 0496.68020 Theor. Comput. Sci. 21, 179-212 (1982). MSC: 68Q65 03D15 03B60 03B45 68N01 PDF BibTeX XML Cite \textit{B. S. Chlebus}, Theor. Comput. Sci. 21, 179--212 (1982; Zbl 0496.68020) Full Text: DOI
Gurari, Eitan M.; Ibarra, Oscar H. Path systems: Constructions, solutions and applications. (English) Zbl 0447.68049 SIAM J. Comput. 9, 348-374 (1980). MSC: 68Q99 68Q05 68Q25 PDF BibTeX XML Cite \textit{E. M. Gurari} and \textit{O. H. Ibarra}, SIAM J. Comput. 9, 348--374 (1980; Zbl 0447.68049) Full Text: DOI
Ruzzo, Walter L. Tree-size bounded alternation. (English) Zbl 0445.68034 J. Comput. Syst. Sci. 21, 218-235 (1980). MSC: 68Q05 68Q25 68Q45 PDF BibTeX XML Cite \textit{W. L. Ruzzo}, J. Comput. Syst. Sci. 21, 218--235 (1980; Zbl 0445.68034) Full Text: DOI
Pratt, Vaughan R. A near-optimal method for reasoning about action. (English) Zbl 0424.03010 J. Comput. Syst. Sci. 20, 231-254 (1980). MSC: 03B45 68Q60 03D15 68Q65 PDF BibTeX XML Cite \textit{V. R. Pratt}, J. Comput. Syst. Sci. 20, 231--254 (1980; Zbl 0424.03010) Full Text: DOI