{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:59:09Z","timestamp":1725890349770},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642316227"},{"type":"electronic","value":"9783642316234"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31623-4_21","type":"book-chapter","created":{"date-parts":[[2012,7,9]],"date-time":"2012-07-09T01:03:34Z","timestamp":1341795814000},"page":"266-279","source":"Crossref","is-referenced-by-count":0,"title":["Bounded Counter Languages"],"prefix":"10.1007","author":[{"given":"Holger","family":"Petersen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","unstructured":"Ben-Amram, A.M., Christensen, N.H., Simonsen, J.G.: Computational models with no linear speedup, Typescript (2011)"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0304-3975(82)90087-1","volume":"21","author":"P. \u010euri\u0161","year":"1982","unstructured":"\u010euri\u0161, P., Galil, Z.: Fooling a two way automaton or one pushdown store is better than one counter for two way machines. Theoretical Computer Science\u00a021, 39\u201353 (1982)","journal-title":"Theoretical Computer Science"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"N.J. Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc.\u00a016, 109\u2013114 (1965)","journal-title":"Proc. Amer. Math. Soc."},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01694011","volume":"2","author":"P.C. Fischer","year":"1968","unstructured":"Fischer, P.C., Meyer, A.R., Rosenberg, A.L.: Counter machines and counter languages. Mathematical Systems Theory\u00a02, 265\u2013283 (1968)","journal-title":"Mathematical Systems Theory"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0304-3975(76)90072-4","volume":"1","author":"S.A. Greibach","year":"1976","unstructured":"Greibach, S.A.: Remarks on the complexity of nondeterministic counter languages. Theoretical Computer Science\u00a01, 269\u2013288 (1976)","journal-title":"Theoretical Computer Science"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0020-0190(93)90078-N","volume":"47","author":"M. H\u00fchne","year":"1993","unstructured":"H\u00fchne, M.: Linear speed-up does not hold on Turing machines with tree storages. Information Processing Letters\u00a047, 313\u2013318 (1993)","journal-title":"Information Processing Letters"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"M.\u00a0Li and P.\u00a0Vit\u00e1nyi. An Introduction to Kolmogorov Complexity and its Applications. Springer (1993)","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M.L. Minsky","year":"1961","unstructured":"Minsky, M.L.: Recursive unsolvability of Post\u2019s problem of \u201ctag\u201d and other topics in theory of Turing machines. Annals of Mathematics\u00a074, 437\u2013455 (1961)","journal-title":"Annals of Mathematics"},{"key":"21_CR9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1051\/ita\/1980140100671","volume":"14","author":"B. Monien","year":"1980","unstructured":"Monien, B.: Two-way multihead automata over a one-letter alphabet. R.A.I.R.O. \u2014 Informatique Th\u00e9orique et Applications\u00a014, 67\u201382 (1980)","journal-title":"R.A.I.R.O. \u2014 Informatique Th\u00e9orique et Applications"},{"key":"#cr-split#-21_CR10.1","unstructured":"Morita, K., Sugata, K., Umeo, H.: Computation complexity of n-bounded counter automaton and multidimensional rebound automaton. Systems Computers Controls\u00a08, 80-87 (1977)"},{"key":"#cr-split#-21_CR10.2","unstructured":"Translated from Denshi Tsushin Gakkai Ronbunshi (IEICE of Japan Trans.) 60-D, 283-290 (1977) (Japanese)"},{"key":"21_CR11","unstructured":"Morita, K., Sugata, K., Umeo, H.: Computational complexity of n-bounded counter automaton and multi-dimensional rebound automaton. IEICE of Japan Trans.\u00a060-E, 226\u2013227 (1977); Abstract of [10]"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1142\/S0129054111008106","volume":"22","author":"H. Petersen","year":"2011","unstructured":"Petersen, H.: Simulations by time-bounded counter machines. International Journal of Foundations of Computer Science\u00a022, 395\u2013409 (2011)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0019-9958(72)90205-7","volume":"20","author":"R.W. Ritchie","year":"1972","unstructured":"Ritchie, R.W., Springsteel, F.N.: Language recognition by marking automata. Information and Control\u00a020, 313\u2013330 (1972)","journal-title":"Information and Control"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Cem Say, A.C., Yakaryilmaz, A.: Quantum counter automata (2011) (submitted for publication)","DOI":"10.1142\/S012905411250013X"},{"key":"21_CR15","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 2nd edn. Thomson (2006)"},{"key":"#cr-split#-21_CR16.1","unstructured":"Sugata, K., Morita, K., Umeo, H.: The language accepted by an n-bounded multicounter automaton and its computing ability. Systems Computers Controls\u00a08, 71-79 (1977)"},{"key":"#cr-split#-21_CR16.2","unstructured":"Translated from Denshi Tsushin Gakkai Ronbunshi (IEICE of Japan Trans.) 60-D, 275-282 (1977) (Japanese)"},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.tcs.2004.07.034","volume":"334","author":"T. Yamasaki","year":"2005","unstructured":"Yamasaki, T., Kobayashi, H., Imai, H.: Quantum versus deterministic counter automata. Theoretical Computer Science\u00a0334, 275\u2013297 (2005)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31623-4_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T01:04:06Z","timestamp":1687568646000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31623-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316227","9783642316234"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31623-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}