{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,13]],"date-time":"2024-01-13T03:22:01Z","timestamp":1705116121830},"reference-count":54,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1989,2,1]],"date-time":"1989-02-01T00:00:00Z","timestamp":602294400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8932,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1989,2]]},"DOI":"10.1016\/0304-3975(89)90078-9","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:48:55Z","timestamp":1027655335000},"page":"203-221","source":"Crossref","is-referenced-by-count":9,"title":["Tradeoffs for language recognition on alternating machines"],"prefix":"10.1016","volume":"63","author":[{"given":"Juraj","family":"Hromkovic\u02c7","sequence":"first","affiliation":[]}],"member":"78","reference":[{"issue":"5","key":"10.1016\/0304-3975(89)90078-9_bib1","first-page":"1033","article-title":"On a method of obtaining lower bounds to the complexity of individual monotone functions","volume":"282","author":"Andreev","year":"1985","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/0304-3975(89)90078-9_bib2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(83)90029-4","article-title":"Boolean functions requiring 3n network size","volume":"28","author":"Blum","year":"1984","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib3","first-page":"294","article-title":"A time-space tradeoff for sorting on a general model of computation","author":"Borodin","year":"1980","journal-title":"Proc. 12th ACMSTOC"},{"key":"10.1016\/0304-3975(89)90078-9_bib4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01752387","article-title":"Three write heads are as good as k","volume":"14","author":"Brandenburg","year":"1981","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0304-3975(89)90078-9_bib5","first-page":"132","article-title":"On one-way auxiliary pushdown automata","volume":"48","author":"Brandenburg","year":"1979"},{"key":"10.1016\/0304-3975(89)90078-9_bib6","first-page":"147","article-title":"Reversal complexity of counter machines","author":"Chan","year":"1981","journal-title":"Proc. 13th Ann. ACMSTOC"},{"key":"10.1016\/0304-3975(89)90078-9_bib7","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(89)90078-9_bib8","series-title":"Proc. 12th ICALP '85","first-page":"101","article-title":"Hierarchies of one-way multihead automata languages","volume":"194","author":"Chrobak","year":"1985"},{"key":"10.1016\/0304-3975(89)90078-9_bib9","first-page":"78","article-title":"The recognition problem for perfect squares","author":"Cobham","year":"1966","journal-title":"Proc. 7th IEEE Symp. on SWAT"},{"key":"10.1016\/0304-3975(89)90078-9_bib10","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1145\/358141.358144","article-title":"An overview of computational complexity","volume":"26","author":"Cook","year":"1983","journal-title":"Comm. ACM"},{"key":"10.1016\/0304-3975(89)90078-9_bib11","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0304-3975(82)90087-1","article-title":"Fooling a two-way automaton or one pushdown store is better than one counter for two-way machines","volume":"21","author":"D\u02c7uris\u02c7","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01744430","article-title":"A time-space tradeoff for language recognition","volume":"17","author":"D\u02c7uris\u02c7","year":"1984","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0304-3975(89)90078-9_bib13","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0019-9958(82)80023-5","article-title":"On reversal-bounded counter machines and on pushdown automata with a bound on the pushdown store","volume":"54","author":"D\u02c7uris\u02c7","year":"1982","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(89)90078-9_bib14","first-page":"127","article-title":"Two nonlinear lower bounds","author":"D\u02c7uris\u02c7","year":"1983","journal-title":"Proc. 15th ACM STOC"},{"key":"10.1016\/0304-3975(89)90078-9_bib15","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0304-3975(83)90096-8","article-title":"One-way simple multihead finite automata are not closed under concatenation","volume":"27","author":"D\u02c7uris\u02c7","year":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib16","first-page":"360","article-title":"Hardware complexity and parallel computation","author":"Dymond","year":"1980","journal-title":"Proc. 21st Ann. IEEE FOCS"},{"key":"10.1016\/0304-3975(89)90078-9_bib17","unstructured":"R. Freivalds, Relation between probabilistic and nondeterministic Turing machines, Unpublished communication presented at the 11th MFCS '84, Prague."},{"key":"10.1016\/0304-3975(89)90078-9_bib18","series-title":"Formal Languages and their Relation to Automata","author":"Hopcroft","year":"1969"},{"key":"10.1016\/0304-3975(89)90078-9_bib19","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/BF00290734","article-title":"One-way multihead deterministic finite automata","volume":"19","author":"Hromkovic\u02c7","year":"1983","journal-title":"Acta Inform."},{"key":"10.1016\/0304-3975(89)90078-9_bib20","series-title":"Proc. 11th MFCS '84","first-page":"312","article-title":"Hierarchy of reversal and zero-testing bounded multicounter machines","volume":"176","author":"Hromkovic\u02c7","year":"1984"},{"key":"10.1016\/0304-3975(89)90078-9_bib21","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/BF00267046","article-title":"Fooling a two-way nondeterministic multihead automaton with reversal number restriction","volume":"22","author":"Hromkovic\u02c7","year":"1985","journal-title":"Acta Inform."},{"key":"10.1016\/0304-3975(89)90078-9_bib22","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/0022-0000(85)90063-7","article-title":"On the power of alternation in automata theory","volume":"31","author":"Hromkovic\u02c7","year":"1985","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib23","first-page":"503","article-title":"On one-way two-head deterministic finite state automata","volume":"4","author":"Hromkovic\u02c7","year":"1985","journal-title":"Computers AI"},{"key":"10.1016\/0304-3975(89)90078-9_bib24","author":"Hromkovic\u02c7","year":"1985","journal-title":"Reversals-Space-Parallelism tradeoff for language recognition"},{"key":"10.1016\/0304-3975(89)90078-9_bib25","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0022-0000(71)80029-6","article-title":"Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata","volume":"5","author":"Ibarra","year":"1971","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib26","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/S0022-0000(73)80048-0","article-title":"On two-way multihead automata","volume":"7","author":"Ibarra","year":"1973","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib27","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288748","article-title":"On 3-head versus 2-head finite automata","volume":"4","author":"Ibarra","year":"1975","journal-title":"Acta Inform."},{"key":"10.1016\/0304-3975(89)90078-9_bib28","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(79)90033-1","article-title":"One-way simple multihead finite automata","volume":"9","author":"Inoue","year":"1979","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib29","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(85)90048-9","article-title":"Alternating simple multihead finite automata","volume":"36","author":"Inoue","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib30","series-title":"Proc. FCT '79","first-page":"214","article-title":"Real-time computations of two-way multihead finite automata","author":"Janiga","year":"1979"},{"key":"10.1016\/0304-3975(89)90078-9_bib31","series-title":"Proc. 8th ICALP '81","first-page":"506","article-title":"Alternating multihead finite automata","volume":"115","author":"King","year":"1981"},{"key":"10.1016\/0304-3975(89)90078-9_bib32","first-page":"120","article-title":"Ob odnom metode sinteza schem","volume":"1","author":"Lupanov","year":"1958","journal-title":"Izv. Vazov Radiofiz."},{"key":"10.1016\/0304-3975(89)90078-9_bib33","first-page":"63","article-title":"O sinteze nekatorych klassov upravljajus\u02c7c\u02c7ich sistem","volume":"10","author":"Lupanov","year":"1963","journal-title":"Problemi Kibernetiki"},{"key":"10.1016\/0304-3975(89)90078-9_bib34","first-page":"401","article-title":"Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines","author":"Maas","year":"1984","journal-title":"Proc. 16th Ann. ACM STOC"},{"key":"10.1016\/0304-3975(89)90078-9_bib35","series-title":"Tech. Rept. 84-591","article-title":"On one tape versus two stacks","author":"Ming","year":"1984"},{"key":"10.1016\/0304-3975(89)90078-9_bib36","first-page":"56","article-title":"Simulating two pushdowns by one tape in n1.5(log2n)0.5time","author":"Ming","year":"1985","journal-title":"Proc. 26th Ann. IEEE FOCS"},{"key":"10.1016\/0304-3975(89)90078-9_bib37","article-title":"Tape versus queue and stack: The lower bounds, Centrum voor Wiskunde en Informatica","author":"Ming","year":"1985","journal-title":"Rept. CS-R8519"},{"key":"10.1016\/0304-3975(89)90078-9_bib38","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1051\/ita\/1980140100671","article-title":"Two-way multihead automata over a one-letter alphabet","volume":"14","author":"Monien","year":"1980","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"10.1016\/0304-3975(89)90078-9_bib39","series-title":"Formal Language Theory, Perspectives and Open Problems","first-page":"287","article-title":"The interface between language theory and complexity theory","author":"Monien","year":"1981"},{"key":"10.1016\/0304-3975(89)90078-9_bib40","first-page":"765","article-title":"A Boolean function","volume":"169","author":"Nec\u02c7iporuk","year":"1966","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/0304-3975(89)90078-9_bib41","series-title":"Proc. 8th ICALP '81","author":"Nigmatulin","year":"1983"},{"key":"10.1016\/0304-3975(89)90078-9_bib42","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0022-0000(79)90028-X","article-title":"On time hierarchies","volume":"19","author":"Paul","year":"1979","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(89)90078-9_bib43","series-title":"Ph.D. Dissertation","article-title":"N-head finite-state machines","author":"Piatkowski","year":"1963"},{"key":"10.1016\/0304-3975(89)90078-9_bib44","series-title":"Proc. 11th MFCS '84","first-page":"480","article-title":"A lower bound on complexity of branching programs","volume":"176","author":"Pudl\u00e1k","year":"1984"},{"key":"10.1016\/0304-3975(89)90078-9_bib45","first-page":"798","article-title":"Lower bounds on the monotone complexity of some Boolean functions","volume":"281","author":"Razborov","year":"1985","journal-title":"Soviet Math. Doklady"},{"key":"10.1016\/0304-3975(89)90078-9_bib46","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/322063.322076","article-title":"k+1 heads are better than k","volume":"25","author":"Rivest","year":"1978","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(89)90078-9_bib47","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1147\/rd.105.0388","article-title":"On multihead finite automata","volume":"10","author":"Rosenberg","year":"1966","journal-title":"IBM J. Res. Develop."},{"key":"10.1016\/0304-3975(89)90078-9_bib48","first-page":"275","article-title":"Nondeterminism and the size of two-way finite automata","author":"Sakoda","year":"1978","journal-title":"Proc. 10th Ann. ACM STOC"},{"key":"10.1016\/0304-3975(89)90078-9_bib49","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0019-9958(74)90994-2","article-title":"Bounded-reversal multihead finite automata languages","volume":"25","author":"Sudborough","year":"1974","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(89)90078-9_bib50","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(76)90426-5","article-title":"One-way multihead writing finite automata","volume":"39","author":"Sudborough","year":"1976","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(89)90078-9_bib51","series-title":"Proc. 11th ICALP '84","first-page":"486","article-title":"The simple roots of real-time computation hierarchies","volume":"172","author":"Vit\u00e1nyi","year":"1984"},{"key":"10.1016\/0304-3975(89)90078-9_bib52","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(85)90039-0","article-title":"Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit","volume":"21","author":"Vit\u00e1nyi","year":"1985","journal-title":"Inform. Process. Lett"},{"key":"10.1016\/0304-3975(89)90078-9_bib53","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(85)90020-1","article-title":"An n1.618 lower bound one the time to simulate one queue or two pushdown stores by one tape","volume":"21","author":"Vit\u00e1nyi","year":"1985","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(89)90078-9_bib54","series-title":"Matematische Monographien","article-title":"Computational Complexity","author":"Wagner","year":"1986"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397589900789?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397589900789?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T15:12:22Z","timestamp":1704208342000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0304397589900789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,2]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1989,2]]}},"alternative-id":["0304397589900789"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(89)90078-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1989,2]]}}}