{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:51Z","timestamp":1725664251366},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_149","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:19:07Z","timestamp":1330262347000},"page":"287-300","source":"Crossref","is-referenced-by-count":2,"title":["A new parallel vector model, with exact characterization of NCk"],"prefix":"10.1007","author":[{"given":"Kenneth W.","family":"Regan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity Theory. Springer Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. M. Barrington","year":"1989","unstructured":"D. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comp. Sys. Sci., 38:150\u2013164, 1989.","journal-title":"J. Comp. Sys. Sci."},{"key":"23_CR3","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"D. M. Barrington","year":"1992","unstructured":"D. Mix Barrington, K. Compton, H. Straubing, and D. Th\u00e9rien. Regular languages in NC1. J. Comp. Sys. Sci., 44:478\u2013499, 1992.","journal-title":"J. Comp. Sys. Sci."},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. M. Barrington","year":"1990","unstructured":"D. Mix Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. J. Comp. Sys. Sci., 41:274\u2013306, 1990.","journal-title":"J. Comp. Sys. Sci."},{"key":"23_CR5","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. M. Barrington","year":"1988","unstructured":"D. Mix Barrington and D. Th\u00e9rien. Finite monoids and the fine structure of NC1. J. ACM, 35:941\u2013952, 1988.","journal-title":"J. ACM"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/0022-0000(85)90015-7","volume":"30","author":"A. Chandra","year":"1985","unstructured":"A. Chandra, S. Fortune, and R. Lipton. Unbounded fan-in circuits and associative functions. J. Comp. Sys. Sci., 30:222\u2013234, 1985.","journal-title":"J. Comp. Sys. Sci."},{"key":"23_CR7","doi-asserted-by":"crossref","first-page":"622","DOI":"10.1137\/0220039","volume":"20","author":"J. Chen","year":"1991","unstructured":"J. Chen and C. Yap. Reversal complexity. SIAM J. Comp., 20:622\u2013638, 1991.","journal-title":"SIAM J. Comp."},{"key":"23_CR8","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook. A taxonomy of problems with fast parallel algorithms. Info. Control, 64:2\u201322, 1985.","journal-title":"Info. Control"},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/BF01185560","volume":"29","author":"T. Harju","year":"1992","unstructured":"T. Harju, H.C.M. Klein, and M. Latteux. Deterministic sequential functions. Acta Informatics, 29:545\u2013554, 1992.","journal-title":"Acta Informatics"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, N. Immerman, and S. Mahaney. One-way log tape reductions. In Proc. 19th FOCS, pages 65\u201372, 1978.","DOI":"10.1109\/SFCS.1978.31"},{"key":"23_CR11","unstructured":"J.-W. Hong. Computation: Similarity and Duality. Research Notes in Theoretical Computer Science. Wiley, 1986."},{"key":"23_CR12","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979."},{"key":"23_CR13","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0019-9958(70)90549-8","volume":"17","author":"T. Kameda","year":"1970","unstructured":"T. Kameda and R. Vollmar. Note on tape reversal complexity of languages. Info. Control, 17:203\u2013215, 1970.","journal-title":"Info. Control"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"R. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, pages 871\u2013941. Elsevier and MIT Press, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"23_CR15","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/BF01212963","volume":"1","author":"P. McKenzie","year":"1991","unstructured":"P. McKenzie, P. P\u00e9ladeau, and D. Th\u00e9rien. NC1: The automata-theoretic viewpoint. Computational Complexity, 1:330\u2013359, 1991.","journal-title":"Computational Complexity"},{"key":"23_CR16","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0020-0190(87)90112-8","volume":"24","author":"I. Parberry","year":"1987","unstructured":"I. Parberry. An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits. Inf. Proc. Lett., 24:363\u2013367, 1987.","journal-title":"Inf. Proc. Lett."},{"key":"23_CR17","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF00264255","volume":"14","author":"W. Paul","year":"1980","unstructured":"W. Paul, E. Prauss, and R. Reischuk. On alternation. Acta Informatica, 14:243\u2013255, 1980.","journal-title":"Acta Informatica"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"N. Pippenger. On simultaneous resource bounds. In Proc. 20th FOCS, pages 307\u2013311, 1979.","DOI":"10.1109\/SFCS.1979.29"},{"key":"23_CR19","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/S0022-0000(76)80037-2","volume":"12","author":"V. Pratt","year":"1976","unstructured":"V. Pratt and L. Stockmeyer. A characterization of the power of vector machines. J. Comp. Sys. Sci., 12:198\u2013221, 1976.","journal-title":"J. Comp. Sys. Sci."},{"key":"23_CR20","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"W. Ruzzo. On uniform circuit complexity. J. Comp. Sys. Sci., 22:365\u2013373, 1981.","journal-title":"J. Comp. Sys. Sci."},{"key":"23_CR21","unstructured":"J. Simon. On some central problems in computational complexity. PhD thesis, Cornell University, 1975."},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"M. Sipser. Borel sets and circuit complexity. In Proc. 15th STOC, pages 61\u201369, 1983.","DOI":"10.1145\/800061.808733"},{"key":"23_CR23","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"L. Stockmeyer and U. Vishkin. Simulations of parallel random access machines by circuits. SIAM J. Comp., 13:409\u2013422, 1984.","journal-title":"SIAM J. Comp."},{"key":"23_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(92)90362-J","volume":"100","author":"J. Trahan","year":"1992","unstructured":"J. Trahan, M. Loui, and V. Ramachandran. Multiplication, division, and shift instructions in parallel random access machines. Theor. Comp. Sci., 100:1\u201344, 1992.","journal-title":"Theor. Comp. Sci."},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"P. van Emde Boas. Machine models and simulations. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, pages 1\u201366. Elsevier and MIT Press, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50006-0"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_149.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:08:02Z","timestamp":1619572082000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_149","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}