{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:50:48Z","timestamp":1725663048017},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_65","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:50:57Z","timestamp":1330195857000},"page":"157-166","source":"Crossref","is-referenced-by-count":4,"title":["Tradeoffs for language recognition on parallel computing models"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Borodin,A.B. \u2014 Cook,S.A. (1980), A time-space tradeoff for sorting on a general model of computation. Proc. 12th ACM STOC, pp.294\u2013301.","DOI":"10.1145\/800141.804677"},{"issue":"1","key":"17_CR2","first-page":"114","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K. \u2014 Kozen, D.C. \u2014 Stockmeyer, L.J. (1981), Alternation. J. ACM 28, 1, pp.114\u2013133.","journal-title":"Alternation. J. ACM"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Cobham,A. (1966), The recognition problem for perfect squares. Proc. 7th IEEE Symp. on SWAT, Berkeley, pp.78\u201387.","DOI":"10.1109\/SWAT.1966.30"},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01744430","volume":"17","author":"P. \u010euri\u0161","year":"1984","unstructured":"\u010euri\u0161, P. \u2014 Galil, Z. (1984), A time-space tradeoff for language recognition. Math. Syst. Theory 17, pp.3\u201312.","journal-title":"Math. Syst. Theory"},{"key":"17_CR5","unstructured":"\u010euris\u0161,P. \u2014 Galil,Z. \u2014 Paul,W. \u2014 Reischuk,R. (1983), Two nonlinear lower bounds. Proc. 15th ACM STOC, pp.127\u2013132."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Dymond,P.W. \u2014 Cook,S.A. (1980), Hardware complexity and parallel computation. Proc. 21th IEEE FOCS, pp.360\u2013372.","DOI":"10.1109\/SFCS.1980.22"},{"key":"17_CR7","unstructured":"Freiwalds,R. (1984), Quadratic lower bound for nondeterministic Turing machines. Short, unpublished communication at the 11th MFCS'84."},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/BF00290734","volume":"19","author":"J. Hromkovi\u010d","year":"1983","unstructured":"Hromkovi\u010d, J. (1983), One-way multihead deterministic finite automata. Acta Informat. 19, 377\u2013384.","journal-title":"Acta Informat."},{"issue":"1","key":"17_CR9","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/0022-0000(85)90063-7","volume":"31","author":"J. Hromkovi\u010d","year":"1985","unstructured":"Hromkovi\u010d, J. (1985), On the power of alternation in automata theory. J. Comput. System Sciences 31, No. 1, 28\u201339.","journal-title":"J. Comput. System Sciences"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/BF00267046","volume":"22","author":"J. Hromkovi\u010d","year":"1985","unstructured":"Hromkovi\u010d, J. (1985), Fooling a two-way multihead automaton with reversal number restriction. Acta Informat. 22, 589\u2013594.","journal-title":"Acta Informat."},{"key":"17_CR11","first-page":"214","volume-title":"Real-time computations of two-way multihead finite automata. Prof. FCT'79","author":"L. Janiga","year":"1979","unstructured":"Janiga, L. (1979), Real-time computations of two-way multihead finite automata. Prof. FCT'79, L. Budach ed., Academic Verlag, Berlin 1979, pp.214\u2013219."},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","volume-title":"Alternating multihead finite automata","author":"K.N. King","year":"1981","unstructured":"King, K.N. (1981), Alternating multihead finite automata. Proc. 8th ICALP, Lecture Notes in Computer Science 115, Springer-Verlag, Berlin-Heidelberg-New York 1981."},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Maas, W. (1984), Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines. Proc. 16th ACM STOC, pp.401\u2013408.","DOI":"10.1145\/800057.808706"},{"key":"17_CR14","first-page":"299","volume":"36","author":"H. Matsuno","year":"1985","unstructured":"Matsuno, H. \u2014 Inoue, K. \u2014 Tanigushi, H. \u2014 Takanami, I. (1985), Alternating simple multihead finite automata, Theoret. Comput. Sci. 36, 299\u2013308.","journal-title":"Comput. Sci."},{"issue":"1\u20133","key":"17_CR15","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/S0019-9958(82)90572-1","volume":"55","author":"A. Ito","year":"1982","unstructured":"Ito, A. \u2014 Inoue, K. \u2014 Takanami, I. \u2014 Tanigushi, H. (1982), Two-dimensional alternating Turing machines with only universal states. Inform. Control 55, Nos. 1\u20133, 193\u2013221.","journal-title":"Inform. Control"},{"key":"17_CR16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0304-3975(83)90093-2","volume":"27","author":"K. Inoue","year":"1983","unstructured":"Inoue, K. \u2014 Takanami, I. \u2014 Tanigushi, H. (1983), Two-dimensional alternating Turing machines. Theoret. Comput. Science 27, 61\u201383.","journal-title":"Theoret. Comput. Science"},{"key":"17_CR17","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0255(85)90042-8","volume":"35","author":"K. Inoue","year":"1985","unstructured":"Inoue, K. \u2014 Ito, A. \u2014 Takanami, I. \u2014 Tanigushi, H. (1985), A spacehierarchy results on two-dimensional alternating Turing machines with only universal states. Information Sciences 35, 79\u201390.","journal-title":"Information Sciences"},{"key":"17_CR18","series-title":"Technical Report","volume-title":"On one tape versus two stacks","author":"M. Li","year":"1984","unstructured":"Li, M. (1984), On one tape versus two stacks. Technical Report 84-591, January 1984, Dept. of Comput. Sci., Cornell University, Ithaca, New York."},{"issue":"2","key":"17_CR19","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/322063.322065","volume":"25","author":"R.L. Rivest","year":"1978","unstructured":"Rivest, R.L. \u2014 Yao, A.C. (1978), k+1 heads are better than k, J. ACM 25, 2, 337\u2013340.","journal-title":"J. ACM"},{"key":"17_CR20","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0019-9958(74)90994-2","volume":"25","author":"I.H. Sudborough","year":"1974","unstructured":"Sudborough, I.H. (1974), Bounded-reversal multihead finite automata languages. Informat. Control 25, pp.317\u2013328.","journal-title":"Informat. Control"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16761-7_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T12:30:59Z","timestamp":1713616259000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}