{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:29:24Z","timestamp":1758274164911},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,11,21]],"date-time":"2009-11-21T00:00:00Z","timestamp":1258761600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s00224-009-9247-x","type":"journal-article","created":{"date-parts":[[2009,11,20]],"date-time":"2009-11-20T20:55:33Z","timestamp":1258750533000},"page":"343-373","source":"Crossref","is-referenced-by-count":4,"title":["A Hierarchy of Monotone Deterministic Non-Forgetting Restarting Automata"],"prefix":"10.1007","volume":"48","author":[{"given":"Hartmut","family":"Messerschmidt","sequence":"first","affiliation":[]},{"given":"Friedrich","family":"Otto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,11,21]]},"reference":[{"key":"9247_CR1","unstructured":"Buntrock, G.: Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t W\u00fcrzburg (1996)"},{"key":"9247_CR2","doi-asserted-by":"crossref","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. Inf. Comput. 141, 1\u201336 (1998)","journal-title":"Inf. Comput."},{"key":"9247_CR3","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/S0022-0000(73)80050-9","volume":"7","author":"K. \u010culik II","year":"1973","unstructured":"\u010culik, K., II, Cohen, R.: LR-regular grammars\u2014an extension of LR(k) grammars. J.\u00a0Comput. Syst. Sci. 7, 66\u201396 (1973)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9247_CR4","doi-asserted-by":"crossref","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.\u00a0Comput. Syst. Sci. 33, 456\u2013472 (1986)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9247_CR5","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/978-3-662-07675-0_4","volume-title":"Handbook of Formal Languages","author":"J. Dassow","year":"1997","unstructured":"Dassow, J., P\u0103un, G., Rozenberg, G.: Grammar systems. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a02, pp. 155\u2013213. Springer, Berlin (1997),"},{"key":"9247_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/3-540-60249-6_60","volume-title":"FCT 1995, Proc.","author":"P. Jan\u010dar","year":"1995","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT 1995, Proc. Lecture Notes in Computer Science, vol.\u00a0965, pp. 283\u2013292. Springer, Berlin (1995)"},{"key":"9247_CR7","series-title":"Lecture Notes in Computer Science","first-page":"401","volume-title":"Theory and Practice of Informatics, SOFSEM\u201996, Proc","author":"P. Jan\u010dar","year":"1996","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M., Vogel, J.: Restarting automata with rewriting. In: Jeffery, K.G., Kr\u00e1l, J., Barto\u0161ek, M. (eds.) Theory and Practice of Informatics, SOFSEM\u201996, Proc. Lecture Notes in Computer Science, vol. 1175, pp. 401\u2013408. Springer, Berlin (1996)"},{"key":"9247_CR8","first-page":"287","volume":"4","author":"P. Jan\u010dar","year":"1999","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M., Vogel, J.: On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4, 287\u2013311 (1999)","journal-title":"J. Autom. Lang. Comb."},{"key":"9247_CR9","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/j.tcs.2006.07.023","volume":"363","author":"T. Jurdzi\u0144ski","year":"2006","unstructured":"Jurdzi\u0144ski, T., Otto, F.: Restarting automata with restricted utilization of auxiliary symbols. Theor. Comput. Sci. 363, 162\u2013181 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9247_CR10","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1142\/S0129054107004723","volume":"18","author":"T. Jurdzi\u0144ski","year":"2007","unstructured":"Jurdzi\u0144ski, T., Otto, F.: Shrinking restarting automata. Int. J. Found. Comput. Sci. 18, 361\u2013385 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9247_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/11505877_25","volume-title":"DLT 2005, Proc","author":"T. Jurdzi\u0144ski","year":"2005","unstructured":"Jurdzi\u0144ski, T., Mr\u00e1z, F., Otto, F., Pl\u00e1tek, M.: Monotone deterministic RL-automata don\u2019t need auxiliary symbols. In: De\u00a0Felice, C., Restivo, A. (eds.) DLT 2005, Proc. Lecture Notes in Computer Science, vol.\u00a03572, pp. 284\u2013295. Springer, Berlin (2005)"},{"key":"9247_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2006.08.029","volume":"369","author":"T. Jurdzi\u0144ski","year":"2006","unstructured":"Jurdzi\u0144ski, T., Mr\u00e1z, F., Otto, F., Pl\u00e1tek, M.: Degrees of non-monotonicity for restarting automata. Theor. Comput. Sci. 369, 1\u201334 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9247_CR13","unstructured":"Lautemann, C.: One pushdown and a small tape. In: Wagner, K.W. (ed.) Dirk Siefkes zum 50. Geburtstag, pp. 42\u201347. Technische Universit\u00e4t Berlin and Universit\u00e4t Augsburg (1988)"},{"key":"9247_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, Berlin (1997)"},{"key":"9247_CR15","first-page":"7","volume":"87","author":"M. Lopatkov\u00e1","year":"2007","unstructured":"Lopatkov\u00e1, M., Pl\u00e1tek, M., Sgall, P.: Towards a formal model for functional generative description: Analysis by reduction and restarting automata. Prague Bull. Math. Linguist. 87, 7\u201326 (2007)","journal-title":"Prague Bull. Math. Linguist."},{"key":"9247_CR16","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. 35, 324\u2013344 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9247_CR17","unstructured":"Messerschmidt, H.: CD-systems of restarting automata. Doctoral Dissertation, Fachbereich Elektrotechnik\/Informatik, Universit\u00e4t Kassel (2008)"},{"key":"9247_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/11753728_26","volume-title":"CSR 2006, Proc.","author":"H. Messerschmidt","year":"2006","unstructured":"Messerschmidt, H., Otto, F.: On non-forgetting restarting automata that are deterministic and\/or monotone. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006, Proc. Lecture Notes in Computer Science, vol.\u00a03967, pp. 247\u2013258. Springer, Berlin (2006)"},{"key":"9247_CR19","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1142\/S0129054107005376","volume":"18","author":"H. Messerschmidt","year":"2007","unstructured":"Messerschmidt, H., Otto, F.: Cooperating distributed systems of restarting automata. Int. J. Found. Comput. Sci. 18, 1333\u20131342 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9247_CR20","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1142\/S0129054109006516","volume":"20","author":"H. Messerschmidt","year":"2009","unstructured":"Messerschmidt, H., Otto, F.: On deterministic CD-systems of restarting automata. Int. J. Found. Comput. Sci. 20, 185\u2013209 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9247_CR21","unstructured":"Narendran, P.: Church-Rosser and related Thue systems. PhD thesis, Rensselaer Polytechnic Institute, Troy, New York (1984)"},{"key":"9247_CR22","first-page":"353","volume-title":"Words, Languages and Combinatorics III, Proc.","author":"G. Niemann","year":"2003","unstructured":"Niemann, G., Otto, F.: Further results on restarting automata. In: Ito, M., Imaoka, T. (eds.) Words, Languages and Combinatorics III, Proc. pp. 353\u2013369. World Scientific, Singapore (2003)"},{"key":"9247_CR23","doi-asserted-by":"crossref","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. Inf. Comput. 197, 1\u201321 (2005)","journal-title":"Inf. Comput."},{"key":"9247_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/978-3-540-39398-6_12","volume-title":"TSD 2003, Proc","author":"K. Oliva","year":"2003","unstructured":"Oliva, K., Kv\u011bto\u0148, P., Ondru\u0161ka, R.: The computational complexity of rule-based part-of-speech tagging. In: Matou\u0161ek, V., Mautner, P. (eds.) TSD 2003, Proc. Lecture Notes in Computer Science, vol.\u00a02807, pp.\u00a082\u201389. Springer, Berlin (2003)"},{"key":"9247_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/3-540-45007-6_5","volume-title":"DLT 2003, Proc","author":"F. Otto","year":"2003","unstructured":"Otto, F.: Restarting automata and their relations to the Chomsky hierarchy. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) DLT 2003, Proc. Lecture Notes in Computer Science, vol.\u00a02710, pp.\u00a055\u201374. Springer, Berlin (2003)"},{"key":"9247_CR26","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1051\/ita\/2009013","volume":"43","author":"F. Otto","year":"2009","unstructured":"Otto, F.: Left-to-right regular languages and two-way restarting automata. RAIRO Theor. Inf. Appl. 43, 653\u2013665 (2009)","journal-title":"RAIRO Theor. Inf. Appl."},{"key":"9247_CR27","series-title":"Studies in Computational Intelligence","first-page":"269","volume-title":"Recent Advances in Formal Languages and Applications","author":"F. Otto","year":"2006","unstructured":"Otto, F.: Restarting automata. In: \u00c9sik, Z., Martin-Vide, C., Mitrana, V. (eds.) Recent Advances in Formal Languages and Applications. Studies in Computational Intelligence, vol.\u00a025, pp.\u00a0269\u2013303. Springer, Berlin (2006)"},{"key":"9247_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/3-540-45627-9_28","volume-title":"SOFSEM\u201901, Proc","author":"M. Pl\u00e1tek","year":"2001","unstructured":"Pl\u00e1tek, M.: Two-way restarting automata and j-monotonicity. In: Pacholski, L., Ru\u017ei\u010dka, P. (eds.) SOFSEM\u201901, Proc. Lecture Notes in Computer Science, vol.\u00a02234, pp.\u00a0316\u2013325. Springer, Berlin (2001)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9247-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9247-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9247-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:38Z","timestamp":1558698698000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9247-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11,21]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9247"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9247-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11,21]]}}}