{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089922},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319602516"},{"type":"electronic","value":"9783319602523"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-60252-3_18","type":"book-chapter","created":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T10:59:13Z","timestamp":1496401153000},"page":"226-237","source":"Crossref","is-referenced-by-count":0,"title":["A Pumping Lemma for Ordered Restarting Automata"],"prefix":"10.1007","author":[{"given":"Kent","family":"Kwee","sequence":"first","affiliation":[]},{"given":"Friedrich","family":"Otto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"key":"18_CR1","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. Comput. Syst. Sci. 33, 456\u2013472 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR2","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"2","author":"G Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. 2, 326\u2013336 (1952)","journal-title":"Proc. Lond. Math. Soc."},{"key":"18_CR3","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1007\/s00224-014-9561-9","volume":"56","author":"P Karandikar","year":"2015","unstructured":"Karandikar, P., Schnoebelen, P.: Generalized Post embedding problems. Theory Comput. Syst. 56, 697\u2013716 (2015)","journal-title":"Theory Comput. Syst."},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-319-19225-3_14","volume-title":"Descriptional Complexity of Formal Systems","author":"K Kwee","year":"2015","unstructured":"Kwee, K., Otto, F.: On some decision problems for stateless deterministic ordered restarting automata. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 165\u2013176. Springer, Cham (2015). doi: 10.1007\/978-3-319-19225-3_14"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-662-49192-8_30","volume-title":"SOFSEM 2016: Theory and Practice of Computer Science","author":"K Kwee","year":"2016","unstructured":"Kwee, K., Otto, F.: On the effects of nondeterminism on ordered restarting automata. In: Freivalds, R.M., Engels, G., Catania, B. (eds.) SOFSEM 2016. LNCS, vol. 9587, pp. 369\u2013380. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49192-8_30"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Kwee, K., Otto, F.: Nondeterministic ordered restarting automata (2017, Submitted)","DOI":"10.1007\/978-3-662-49192-8_30"},{"key":"18_CR8","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":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-319-04298-5_38","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"F Mr\u00e1z","year":"2014","unstructured":"Mr\u00e1z, F., Otto, F.: Ordered restarting automata for picture languages. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 431\u2013442. Springer, Cham (2014). doi: 10.1007\/978-3-319-04298-5_38"},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1023\/A:1009918602528","volume":"2","author":"F Mr\u00e1z","year":"1999","unstructured":"Mr\u00e1z, F., Pl\u00e1tek, M., Proch\u00e1zka, M.: On special forms of restarting automata. Grammars 2, 223\u2013233 (1999)","journal-title":"Grammars"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-319-09704-6_28","volume-title":"Descriptional Complexity of Formal Systems","author":"F Otto","year":"2014","unstructured":"Otto, F.: On the descriptional complexity of deterministic ordered restarting automata. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 318\u2013329. Springer, Cham (2014). doi: 10.1007\/978-3-319-09704-6_28"},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-642-22012-8_35","volume-title":"Automata, Languages and Programming","author":"S Schmitz","year":"2011","unstructured":"Schmitz, S., Schnoebelen, P.: Multiply-recursive upper bounds with Higman\u2019s lemma. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 441\u2013452. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22012-8_35"}],"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-319-60252-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T09:31:56Z","timestamp":1569403916000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-60252-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319602516","9783319602523"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60252-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}