{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:55:34Z","timestamp":1775818534084,"version":"3.50.1"},"reference-count":64,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2015,1,2]],"date-time":"2015-01-02T00:00:00Z","timestamp":1420156800000},"content-version":"vor","delay-in-days":1462,"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":[[2011,1]]},"DOI":"10.1016\/j.tcs.2010.08.024","type":"journal-article","created":{"date-parts":[[2010,9,4]],"date-time":"2010-09-04T11:10:01Z","timestamp":1283598601000},"page":"83-96","source":"Crossref","is-referenced-by-count":40,"title":["Complexity of multi-head finite automata: Origins and directions"],"prefix":"10.1016","volume":"412","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Malcher","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2010.08.024_br000005","unstructured":"P. Berman, A. Lingas, On the complexity of regular languages in terms of finite automata, Technical Report 304, Polish Academy of Sciences, 1977."},{"key":"10.1016\/j.tcs.2010.08.024_br000010","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF01371727","article-title":"State-complexity of finite-state devices, state compressibility and incompressibility","volume":"26","author":"Birget","year":"1993","journal-title":"Math. Systems Theory"},{"key":"10.1016\/j.tcs.2010.08.024_br000015","series-title":"Developments in Language Theory","article-title":"On the computational capacity of parallel communicating finite automata","volume":"vol. 5257","author":"Bordihn","year":"2008"},{"key":"10.1016\/j.tcs.2010.08.024_br000020","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1145\/322374.322380","article-title":"On communicating finite-state machines","volume":"30","author":"Brand","year":"1983","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2010.08.024_br000025","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0020-0190(87)90172-4","article-title":"Multiprocessor automata","volume":"25","author":"Buda","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.tcs.2010.08.024_br000030","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1997.2681","article-title":"Growing context-sensitive languages and Church-Rosser languages","volume":"141","author":"Buntrock","year":"1998","journal-title":"Inform. Comput."},{"key":"10.1016\/j.tcs.2010.08.024_br000035","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1051\/ita:2007014","article-title":"Returning and non-returning parallel communicating finite automata are equivalent","volume":"41","author":"Choudhary","year":"2007","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"10.1016\/j.tcs.2010.08.024_br000040","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","article-title":"Finite automata and unary languages","volume":"47","author":"Chrobak","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000045","series-title":"International Colloquium on Automata, Languages and Programming","article-title":"Power of cooperation and multihead finite systems","volume":"vol. 1443","author":"\u010euri\u0161","year":"1998"},{"key":"10.1016\/j.tcs.2010.08.024_br000050","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0304-3975(02)00403-6","article-title":"Converting two-way nondeterministic unary automata into simpler automata","volume":"295","author":"Geffert","year":"2003","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000055","series-title":"The Mathematical Theory of Context-Free Languages","author":"Ginsburg","year":"1966"},{"key":"10.1016\/j.tcs.2010.08.024_br000060","first-page":"193","article-title":"Descriptional complexity of machines with limited resources","volume":"8","author":"Goldstine","year":"2002","journal-title":"J. UCS"},{"key":"10.1016\/j.tcs.2010.08.024_br000065","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1090\/psapm\/019\/0235938","article-title":"Context-free languages and Turing machine computations","volume":"19","author":"Hartmanis","year":"1967","journal-title":"Proc. Symposia Appl. Math."},{"key":"10.1016\/j.tcs.2010.08.024_br000070","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/BF00289513","article-title":"On non-determinancy in simple computing devices","volume":"1","author":"Hartmanis","year":"1972","journal-title":"Acta Inform."},{"key":"10.1016\/j.tcs.2010.08.024_br000075","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1137\/0209010","article-title":"On the succinctness of different representations of languages","volume":"9","author":"Hartmanis","year":"1980","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2010.08.024_br000080","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(83)90016-6","article-title":"On G\u00f6del speed-up and succinctness of language representations","volume":"26","author":"Hartmanis","year":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000085","unstructured":"M. Holzer, Data-independent versus data-dependent computations on multi-head automata, Doctoral Thesis, Universit\u00e4t T\u00fcbingen, 1998."},{"key":"10.1016\/j.tcs.2010.08.024_br000090","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0304-3975(01)00237-7","article-title":"Multi-head finite automata: data-independent versus data-dependent computations","volume":"286","author":"Holzer","year":"2002","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000095","series-title":"Introduction to Automata Theory, Language, and Computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/j.tcs.2010.08.024_br000100","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":"Hromkovi\u010d","year":"1985","journal-title":"Acta Inform."},{"key":"10.1016\/j.tcs.2010.08.024_br000105","series-title":"International Colloquium on Automata, Languages and Programming","article-title":"Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser\u2019s separation","volume":"vol. 2719","author":"Hromkovi\u010d","year":"2003"},{"key":"10.1016\/j.tcs.2010.08.024_br000110","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0020-0190(74)90043-X","article-title":"A note on semilinear sets and bounded-reversal multihead pushdown automata","volume":"3","author":"Ibarra","year":"1974","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.tcs.2010.08.024_br000115","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/322047.322058","article-title":"Reversal-bounded multicounter machines and their decision problems","volume":"25","author":"Ibarra","year":"1978","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2010.08.024_br000120","unstructured":"O.H. Ibarra, J. Karhum\u00e4ki, A. Okhotin, On stateless multihead automata: hierarchies and the emptiness problem, TUCS Technical Report 848, Turku Centre for Computer Science, 2007."},{"key":"10.1016\/j.tcs.2010.08.024_br000125","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF00288748","article-title":"On 3-head versus 2-head finite automata","volume":"4","author":"Ibarra","year":"1974","journal-title":"Acta Inform."},{"key":"10.1016\/j.tcs.2010.08.024_br000130","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0022-0000(76)80026-8","article-title":"A useful device for showing the solvability of some decision problems","volume":"13","author":"Ibarra","year":"1976","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000135","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/j.tcs.2006.01.030","article-title":"On partially blind multihead finite automata","volume":"356","author":"Ibarra","year":"2006","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000140","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1142\/S012905410500339X","article-title":"Non-recursive trade-offs for two-way machines","volume":"16","author":"Kapoutsis","year":"2005","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000145","series-title":"Mathematical Foundations of Computer Science","article-title":"Removing bidirectionality from nondeterministic finite automata","volume":"vol. 3618","author":"Kapoutsis","year":"2005"},{"key":"10.1016\/j.tcs.2010.08.024_br000150","unstructured":"R. Klemm, Systems of communicating finite state machines as a distributed alternative to finite state machines, Ph.D. Thesis, Pennsylvania State University, 1996."},{"key":"10.1016\/j.tcs.2010.08.024_br000155","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0019-9958(64)90120-2","article-title":"Classes of languages and linear-bounded automata","volume":"7","author":"Kuroda","year":"1964","journal-title":"Inform. Control"},{"key":"10.1016\/j.tcs.2010.08.024_br000160","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/j.tcs.2004.04.013","article-title":"On the descriptional power of heads, counters, and pebbles","volume":"330","author":"Kutrib","year":"2005","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000165","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1142\/S0129054105003406","article-title":"The phenomenon of non-recursive trade-offs","volume":"16","author":"Kutrib","year":"2005","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000170","series-title":"Foundations of Software Technology and Theoretical Computer Science","article-title":"Data-independences of parallel random access machines","volume":"vol. 761","author":"Lange","year":"1993"},{"key":"10.1016\/j.tcs.2010.08.024_br000175","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1006\/jcss.2001.1783","article-title":"Tight lower bounds on the size of sweeping automata","volume":"63","author":"Leung","year":"2001","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000180","series-title":"Developments in Language Theory","article-title":"Descriptional complexity of bounded context-free languages","volume":"vol. 4588","author":"Malcher","year":"2007"},{"key":"10.1016\/j.tcs.2010.08.024_br000185","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1142\/S0129054102001424","article-title":"Parallel finite automata systems communicating by states","volume":"13","author":"Mart\u00edn-Vide","year":"2002","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000190","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/42282.42284","article-title":"Church-Rosser Thue systems and formal languages","volume":"35","author":"McNaughton","year":"1988","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2010.08.024_br000195","series-title":"IEEE Symposium on Switching and Automata Theory","article-title":"Economy of description by automata, grammars, and formal systems","author":"Meyer","year":"1971"},{"key":"10.1016\/j.tcs.2010.08.024_br000200","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\/j.tcs.2010.08.024_br000205","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","article-title":"On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata","volume":"20","author":"Moore","year":"1971","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/j.tcs.2010.08.024_br000210","first-page":"80","article-title":"Computation complexity of n-bounded counter automaton and multidimensional rebound automaton","volume":"8","author":"Morita","year":"1977","journal-title":"Syst. Comput. Controls"},{"key":"10.1016\/j.tcs.2010.08.024_br000215","first-page":"283","article-title":"Computation complexity of n-bounded counter automaton and multidimensional rebound automaton","volume":"60-D","author":"Morita","year":"1977","journal-title":"Denshi Tsushin Gakkai Ronbunshi"},{"key":"10.1016\/j.tcs.2010.08.024_br000220","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/321356.321364","article-title":"On context-free languages","volume":"13","author":"Parikh","year":"1966","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2010.08.024_br000225","series-title":"Complexity of Computation","article-title":"An improved overlap argument for on-line multiplication","volume":"vol. 7","author":"Paterson","year":"1974"},{"key":"10.1016\/j.tcs.2010.08.024_br000230","series-title":"Proceedings of the Third Israel Symposium on the Theory of Computing and Systems","article-title":"Automata with sensing heads","author":"Petersen","year":"1995"},{"key":"10.1016\/j.tcs.2010.08.024_br000235","series-title":"Mathematical Foundations of Computer Science","article-title":"The head hierarchy for oblivious finite automata with polynomial advice collapses","volume":"vol. 1450","author":"Petersen","year":"1998"},{"key":"10.1016\/j.tcs.2010.08.024_br000240","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","article-title":"Relations among complexity measures","volume":"26","author":"Pippenger","year":"1979","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2010.08.024_br000245","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","article-title":"Finite automata and their decision problems","volume":"3","author":"Rabin","year":"1959","journal-title":"IBM J. Res. Dev."},{"key":"10.1016\/j.tcs.2010.08.024_br000250","series-title":"Sequential Machines \u2014 Selected Papers","first-page":"63","article-title":"Finite automata and their decision problems","author":"Rabin","year":"1964"},{"key":"10.1016\/j.tcs.2010.08.024_br000255","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0019-9958(72)90205-7","article-title":"Language recognition by marking automata","volume":"20","author":"Ritchie","year":"1972","journal-title":"Inform. Control"},{"key":"10.1016\/j.tcs.2010.08.024_br000260","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1147\/rd.105.0388","article-title":"On multi-head finite automata","volume":"10","author":"Rosenberg","year":"1966","journal-title":"IBM J. Res. Dev."},{"key":"10.1016\/j.tcs.2010.08.024_br000265","series-title":"Symposium on Theory of Computing","article-title":"Nondeterminism and the size of two way finite automata","author":"Sakoda","year":"1978"},{"key":"10.1016\/j.tcs.2010.08.024_br000270","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1137\/0206039","article-title":"Succinctness of descriptions of unambiguous context-free languages","volume":"6","author":"Schmidt","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2010.08.024_br000275","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF00265223","article-title":"The network complexity and the Turing machine complexity of finite functions","volume":"7","author":"Schnorr","year":"1976","journal-title":"Acta Inform."},{"key":"10.1016\/j.tcs.2010.08.024_br000280","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.32.0198","article-title":"The reduction of two-way automata to one-way automata","volume":"3","author":"Shepherdson","year":"1959","journal-title":"IBM J. Res. Dev."},{"key":"10.1016\/j.tcs.2010.08.024_br000285","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","article-title":"Lower bounds on the size of sweeping automata","volume":"21","author":"Sipser","year":"1980","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000290","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0019-9958(67)90591-8","article-title":"A regularity test for pushdown machines","volume":"11","author":"Stearns","year":"1967","journal-title":"Inform. Control"},{"key":"10.1016\/j.tcs.2010.08.024_br000295","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. Control"},{"key":"10.1016\/j.tcs.2010.08.024_br000300","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","article-title":"On tape-bounded complexity classes and multihead finite automata","volume":"10","author":"Sudborough","year":"1975","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.tcs.2010.08.024_br000305","first-page":"11","article-title":"The language accepted by a rebound automaton and its computing ability","volume":"60-A","author":"Sugata","year":"1977","journal-title":"Electron. Commun. Japan"},{"key":"10.1016\/j.tcs.2010.08.024_br000310","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0019-9958(76)90173-X","article-title":"A note on the succinctness of descriptions of deterministic languages","volume":"32","author":"Valiant","year":"1976","journal-title":"Inform. Control"},{"key":"10.1016\/j.tcs.2010.08.024_br000315","series-title":"Computational Complexity","author":"Wagner","year":"1986"},{"key":"10.1016\/j.tcs.2010.08.024_br000320","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/322063.322076","article-title":"k+1 heads are better than k","volume":"25","author":"Yao","year":"1978","journal-title":"J. ACM"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397510004597?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397510004597?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T04:04:23Z","timestamp":1711771463000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397510004597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":64,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["S0304397510004597"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2010.08.024","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}