{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:17:50Z","timestamp":1725560270451},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281931"},{"type":"electronic","value":"9783540318736"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11537311_27","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T14:00:06Z","timestamp":1127829606000},"page":"305-316","source":"Crossref","is-referenced-by-count":1,"title":["Shrinking Multi-pushdown Automata"],"prefix":"10.1007","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[]},{"given":"Friedrich","family":"Otto","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","first-page":"75","volume-title":"Complexity of Computation, SIAM-AMS Symp. in Appl. Math.","author":"S.O. Aanderaa","year":"1974","unstructured":"Aanderaa, S.O.: On k-tape versus (k\u22121)-tape real time computation. In: Karp, R.M. (ed.) Complexity of Computation, SIAM-AMS Symp. in Appl. Math., vol.\u00a07, pp. 75\u201396. American Math. Society, Providence (1974)"},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/S0022-0000(71)80025-9","volume":"5","author":"R.V. Book","year":"1971","unstructured":"Book, R.V.: Time-bounded grammars and their languages. J. Comput. System Sci.\u00a05, 397\u2013429 (1971)","journal-title":"J. Comput. System Sci."},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R.V. Book","year":"1970","unstructured":"Book, R.V., Greibach, S.A.: Quasi-realtime languages. Math. Systems Theory\u00a04, 97\u2013111 (1970)","journal-title":"Math. Systems Theory"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-540-30550-7_9","volume-title":"Developments in Language Theory","author":"H. Bordihn","year":"2004","unstructured":"Bordihn, H., Holzer, M., Kutrib, M.: Input reversals and iterated pushdown automata: A new characterization of khabbaz geometric hierarchy of languages. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol.\u00a03340, pp. 102\u2013113. Springer, Heidelberg (2004)"},{"key":"27_CR5","unstructured":"Buntrock, G.: Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t W\u00fcrzburg (1996)"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1997.2681","volume":"141","author":"G. Buntrock","year":"1998","unstructured":"Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Inform. and Comput.\u00a0141, 1\u201336 (1998)","journal-title":"Inform. and Comput."},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"E. Dahlhaus","year":"1986","unstructured":"Dahlhaus, E., Warmuth, M.: Membership for growing context-sensitive grammars is polynomial. J. Comput. System Sci.\u00a033, 456\u2013472 (1986)","journal-title":"J. Comput. System Sci."},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/3-540-45061-0_40","volume-title":"ICALP 2003, Proc.","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better Than k. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 490\u2013501. Springer, Heidelberg (2003)"},{"key":"27_CR9","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/42282.42284","volume":"35","author":"R. McNaughton","year":"1988","unstructured":"McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach.\u00a035, 324\u2013344 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2004.09.003","volume":"197","author":"G. Niemann","year":"2005","unstructured":"Niemann, G., Otto, F.: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. FOSSACS 1998\u00a0197, 1\u201321 (2005); An extended abstract appeared in Nivat, M. (ed.) FoSSaCS 1998. LNCS, vol. 1378, pp. 243\u2013257. Springer, Berlin (1998)","journal-title":"Inform. and Comput."},{"key":"27_CR12","unstructured":"Otto, F., Moriya, E.: Shrinking alternating two-pushdown automata. IEICE Trans. on Inform. and Systems\u00a0E87-D, 959\u2013966 (2004)"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(82)91055-5","volume":"53","author":"W.J. Paul","year":"1982","unstructured":"Paul, W.J.: On-line simulation of k + 1 tapes by k tapes requires nonlinear time. Inform. and Control\u00a053, 1\u20138 (1982)","journal-title":"Inform. and Control"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF00264255","volume":"14","author":"W.J. Paul","year":"1980","unstructured":"Paul, W.J., Prau\u00df, E., Reischuk, R.: On alternation. Acta Inform.\u00a014, 243\u2013255 (1980)","journal-title":"Acta Inform."},{"key":"27_CR15","first-page":"429","volume-title":"24th Annual Symposium on Foundations of Computer Science, Proc.","author":"W.J. Paul","year":"1983","unstructured":"Paul, W.J., Pippenger, N., Szemer\u00e9di, E., Trotter, W.T.: On determinism versus non-determinism and related problems. In: 24th Annual Symposium on Foundations of Computer Science, Proc., pp. 429\u2013438. IEEE Computer Society, Los Angeles (1983)"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11537311_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:52:43Z","timestamp":1619506363000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11537311_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281931","9783540318736"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11537311_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}