{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:50Z","timestamp":1760202650336},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642370748"},{"type":"electronic","value":"9783642370755"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-37075-5_18","type":"book-chapter","created":{"date-parts":[[2013,2,18]],"date-time":"2013-02-18T19:37:23Z","timestamp":1361216243000},"page":"273-288","source":"Crossref","is-referenced-by-count":5,"title":["The Parametric Ordinal-Recursive Complexity of Post Embedding Problems"],"prefix":"10.1007","author":[{"given":"Prateek","family":"Karandikar","sequence":"first","affiliation":[]},{"given":"Sylvain","family":"Schmitz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1006\/inco.1999.2843","volume":"160","author":"P.A. Abdulla","year":"2000","unstructured":"Abdulla, P.A., \u010cer\u0101ns, K., Jonsson, B., Tsay, Y.K.: Algorithmic analysis of programs with well quasi-ordered domains. Inform. and Comput.\u00a0160, 109\u2013127 (2000)","journal-title":"Inform. and Comput."},{"issue":"2","key":"18_CR2","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1006\/inco.1996.0053","volume":"127","author":"P.A. Abdulla","year":"1996","unstructured":"Abdulla, P.A., Jonsson, B.: Verifying programs with unreliable channels. Inform. and Comput.\u00a0127(2), 91\u2013101 (1996)","journal-title":"Inform. and Comput."},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Atig, M.F., Bouajjani, A., Burckhardt, S., Musuvathi, M.: On the verification problem for weak memory models. In: POPL 2010, pp. 7\u201318. ACM (2010)","DOI":"10.1145\/1707801.1706303"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Barcel\u00f3, P., Figueira, D., Libkin, L.: Graph logics with rational relations and the generalized intersection problem. In: LICS 2012, pp. 115\u2013124. IEEE Press (2012)","DOI":"10.1109\/LICS.2012.23"},{"issue":"4","key":"18_CR5","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s00165-012-0234-7","volume":"24","author":"P. Bouyer","year":"2012","unstructured":"Bouyer, P., Markey, N., Ouaknine, J., Schnoebelen, P., Worrell, J.: On termination and invariance for faulty channel machines. Form. Asp. Comput.\u00a024(4), 595\u2013607 (2012)","journal-title":"Form. Asp. Comput."},{"issue":"1","key":"18_CR6","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/inco.1996.0003","volume":"124","author":"G. C\u00e9c\u00e9","year":"1996","unstructured":"C\u00e9c\u00e9, G., Finkel, A., Purushothaman Iyer, S.: Unreliable channels are easier to verify than perfect channels. Inform. and Comput.\u00a0124(1), 20\u201331 (1996)","journal-title":"Inform. and Comput."},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-540-77050-3_22","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science","author":"P. Chambart","year":"2007","unstructured":"Chambart, P., Schnoebelen, P.: Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol.\u00a04855, pp. 265\u2013276. Springer, Heidelberg (2007)"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-540-85361-9_28","volume-title":"CONCUR 2008 - Concurrency Theory","author":"P. Chambart","year":"2008","unstructured":"Chambart, P., Schnoebelen, P.: Mixing Lossy and Perfect Fifo Channels. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol.\u00a05201, pp. 340\u2013355. Springer, Heidelberg (2008)"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Chambart, P., Schnoebelen, P.: The ordinal recursive complexity of lossy channel systems. In: LICS 2008, pp. 205\u2013216. IEEE Press (2008)","DOI":"10.1109\/LICS.2008.47"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/978-3-642-14162-1_6","volume-title":"Automata, Languages and Programming","author":"P. Chambart","year":"2010","unstructured":"Chambart, P., Schnoebelen, P.: Pumping and Counting on the Regular Post Embedding Problem. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06199, pp. 64\u201375. Springer, Heidelberg (2010)"},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1147\/rd.91.0047","volume":"9","author":"C.C. Elgot","year":"1965","unstructured":"Elgot, C.C., Mezei, J.E.: On relations defined by generalized finite automata. IBM Journal of Research and Development\u00a09(1), 47\u201368 (1965)","journal-title":"IBM Journal of Research and Development"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Fairtlough, M., Wainer, S.S.: Hierarchies of provably recursive functions. In: Handbook of Proof Theory, ch. III, pp. 149\u2013207. Elsevier (1998)","DOI":"10.1016\/S0049-237X(98)80018-9"},{"issue":"1-2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(00)00102-X","volume":"256","author":"A. Finkel","year":"2001","unstructured":"Finkel, A., Schnoebelen, P.: Well-structured transition systems everywhere! Theor. Comput. Sci.\u00a0256(1-2), 63\u201392 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR14","unstructured":"Friedman, H.M.: Some decision problems of enormous complexity. In: LICS 1999, pp. 2\u201313. IEEE Press (1999)"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Haddad, S., Schmitz, S., Schnoebelen, P.: The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets. In: LICS 2012, pp. 355\u2013364. IEEE Press (2012)","DOI":"10.1109\/LICS.2012.46"},{"key":"18_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-642-33475-7_11","volume-title":"Theoretical Computer Science","author":"P. Jan\u010dar","year":"2012","unstructured":"Jan\u010dar, P., Karandikar, P., Schnoebelen, P.: Unidirectional Channel Systems Can Be Tested. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds.) TCS 2012. LNCS, vol.\u00a07604, pp. 149\u2013163. Springer, Heidelberg (2012)"},{"key":"18_CR17","unstructured":"Jenkins, M.: Synthesis and Alternating Automata over Real Time. Ph.D. thesis, Oxford University (2012)"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-642-30642-6_22","volume-title":"Computer Science \u2013 Theory and Applications","author":"P. Karandikar","year":"2012","unstructured":"Karandikar, P., Schnoebelen, P.: Cutting through Regular Post Embedding Problems. In: Hirsch, E.A., Karhum\u00e4ki, J., Lepist\u00f6, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol.\u00a07353, pp. 229\u2013240. Springer, Heidelberg (2012)"},{"issue":"2","key":"18_CR19","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/1342991.1342994","volume":"9","author":"S. Lasota","year":"2008","unstructured":"Lasota, S., Walukiewicz, I.: Alternating timed automata. ACM Trans. Comput. Logic\u00a09(2), 10 (2008)","journal-title":"ACM Trans. Comput. Logic"},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/BFb0036926","volume-title":"Automata, Languages and Programming","author":"M. Latteux","year":"1983","unstructured":"Latteux, M., Leguy, J.: On the Composition of Morphisms and Inverse Morphisms. In: D\u00edaz, J. (ed.) ICALP 1983. LNCS, vol.\u00a0154, pp. 420\u2013432. Springer, Heidelberg (1983)"},{"key":"18_CR21","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF01967649","volume":"13","author":"M. L\u00f6b","year":"1970","unstructured":"L\u00f6b, M., Wainer, S.: Hierarchies of number theoretic functions, I. Arch. Math. Logic\u00a013, 39\u201351 (1970)","journal-title":"Arch. Math. Logic"},{"key":"18_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/11691372_27","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"J. Ouaknine","year":"2006","unstructured":"Ouaknine, J., Worrell, J.B.: Safety Metric Temporal Logic Is Fully Decidable. In: Hermanns, H., Palsberg, J. (eds.) TACAS 2006. LNCS, vol.\u00a03920, pp. 411\u2013425. Springer, Heidelberg (2006)"},{"issue":"1","key":"18_CR23","first-page":"8","volume":"3","author":"J.O. Ouaknine","year":"2007","unstructured":"Ouaknine, J.O., Worrell, J.B.: On the decidability and complexity of Metric Temporal Logic over finite words. Logic. Meth. in Comput. Sci.\u00a03(1), 8 (2007)","journal-title":"Logic. Meth. in Comput. Sci."},{"key":"18_CR24","unstructured":"Rose, H.E.: Subrecursion: Functions and Hierarchies, Oxford Logic Guides, vol.\u00a09. Clarendon Press (1984)"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press (2009)","DOI":"10.1017\/CBO9781139195218"},{"key":"18_CR26","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, Part II. LNCS, vol.\u00a06756, pp. 441\u2013452. Springer, Heidelberg (2011)"},{"key":"18_CR27","unstructured":"Schmitz, S., Schnoebelen, P.: Algorithmic Aspects of WQO Theory. Lecture Notes (2012), \n                    \n                      http:\/\/cel.archives-ouvertes.fr\/cel-00727025"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-37075-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T08:44:25Z","timestamp":1557564265000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-37075-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642370748","9783642370755"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-37075-5_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}