{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:09:23Z","timestamp":1725559763553},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540275800"},{"type":"electronic","value":"9783540316916"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_117","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T18:58:59Z","timestamp":1279479539000},"page":"1450-1461","source":"Crossref","is-referenced-by-count":32,"title":["Unsafe Grammars and Panic Automata"],"prefix":"10.1007","author":[{"given":"Teodor","family":"Knapik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damian","family":"Niwi\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Urzyczyn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Walukiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"117_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-540-31982-5_31","volume-title":"Foundations of Software Science and Computational Structures","author":"K. Aehlig","year":"2005","unstructured":"Aehlig, K., de Miranda, J.G., Ong, L.: Safety is not a restriction at level 2 for string languages. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol.\u00a03441, pp. 490\u2013504. Springer, Heidelberg (2005)"},{"key":"117_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/11417170_5","volume-title":"Typed Lambda Calculi and Applications","author":"K. Aehlig","year":"2005","unstructured":"Aehlig, K., de Miranda, J.G., Ong, L.: The monadic second order theory of trees given by arbitrary level-two recursion schemes is decidable. In: Urzyczyn, P. (ed.) TLCA 2005. LNCS, vol.\u00a03461, pp. 39\u201354. Springer, Heidelberg (2005)"},{"key":"117_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/3-540-45061-0_45","volume-title":"Automata, Languages and Programming","author":"T. Cachat","year":"2003","unstructured":"Cachat, T.: Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 556\u2013569. Springer, Heidelberg (2003)"},{"key":"117_CR4","unstructured":"Cachat, T., Walukiewicz, I.: The complexity of games on higher order pushdown automata, (2004) (manuscript)"},{"key":"117_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/3-540-45687-2_13","volume-title":"Mathematical Foundations of Computer Science 2002","author":"D. Caucal","year":"2002","unstructured":"Caucal, D.: On infinite terms having a decidable monadic second-order theory. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 165\u2013176. Springer, Heidelberg (2002)"},{"key":"117_CR6","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(95)00049-3","volume":"151","author":"B. Courcelle","year":"1995","unstructured":"Courcelle, B.: The monadic second-order theory of graphs IX: Machines and their behaviours. Theoretical Comput. Sci.\u00a0151, 125\u2013162 (1995)","journal-title":"Theoretical Comput. Sci."},{"issue":"1-2","key":"117_CR7","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0304-3975(02)00012-9","volume":"281","author":"B. Courcelle","year":"2002","unstructured":"Courcelle, B., Knapik, T.: The evaluation of if first-order substitution is monadic second-order compatible. Theoretical Comput. Sci.\u00a0281(1-2), 177\u2013206 (2002)","journal-title":"Theoretical Comput. Sci."},{"issue":"2","key":"117_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0304-3975(82)90009-3","volume":"20","author":"W. Damm","year":"1982","unstructured":"Damm, W.: The IO- and OI-hierarchies. Theoretical Comput. Sci.\u00a020(2), 195\u2013208 (1982)","journal-title":"Theoretical Comput. Sci."},{"key":"117_CR9","first-page":"368","volume-title":"Proceedings 32th Annual IEEE Symp. on Foundations of Comput.\u00a0Sci.","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy. In: Proceedings 32th Annual IEEE Symp. on Foundations of Comput.\u00a0Sci., pp. 368\u2013377. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"117_CR10","doi-asserted-by":"crossref","unstructured":"Engelfriet, J.: Iterated push-down automata and complexity classes. In: Proc.\u00a015th STOC, pp. 365\u2013373 (1983)","DOI":"10.1145\/800061.808767"},{"issue":"3","key":"117_CR11","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/S0022-0000(77)80034-2","volume":"15","author":"J. Engelfriet","year":"1977","unstructured":"Engelfriet, J., Schmidt, E.M.: IO and OI. J.\u00a0Comput.\u00a0System Sci.\u00a015(3), 328\u2013353 (1977); 16(1), 67\u201399 (1978)","journal-title":"J. Comput. System Sci."},{"key":"117_CR12","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Logics, and Infinite Games. A Guide to Current Research","year":"2002","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games. A Guide to Current Research. LNCS, vol.\u00a01500. Springer, Heidelberg (2002)"},{"key":"117_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/3-540-45413-6_21","volume-title":"Typed Lambda Calculi and Applications","author":"T. Knapik","year":"2001","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P.: Deciding monadic theories of hyperalgebraic trees. In: Abramsky, S. (ed.) TLCA 2001. LNCS, vol.\u00a02044, pp. 253\u2013267. Springer, Heidelberg (2001)"},{"key":"117_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-45931-6_15","volume-title":"Foundations of Software Science and Computation Structures","author":"T. Knapik","year":"2002","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P.: Higher-order pushdown trees are easy. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. LNCS, vol.\u00a02303, pp. 205\u2013222. Springer, Heidelberg (2002)"},{"key":"117_CR15","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P., Walukiewicz, I.: Unsafe grammars and panic automata, draft, http:\/\/www.mimuw.edu.pl\/~niwinski\/prace.html"},{"key":"117_CR16","first-page":"1170","volume":"15","author":"A.N. Maslov","year":"1974","unstructured":"Maslov, A.N.: The hierarchy of indexed languages of an arbitrary level. Soviet Math.\u00a0Dokl.\u00a015, 1170\u20131174 (1974)","journal-title":"Soviet Math.\u00a0Dokl."},{"key":"117_CR17","unstructured":"Mostowski, A.W.: Games with forbidden positions. Technical Report 78, Instytut Matematyki, University of Gdansk (1991)"},{"key":"117_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00039-X","volume":"189","author":"D. Niwi\u0144ski","year":"1997","unstructured":"Niwi\u0144ski, D.: Fixed points characterization of infinite behaviour of finite state systems. Theoret.\u00a0Comput.\u00a0Sci.\u00a0189, 1\u201369 (1997)","journal-title":"Theoret.\u00a0Comput.\u00a0Sci."},{"key":"117_CR19","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Languages","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a03, pp. 389\u2013455. Springer, Heidelberg (1997)"},{"issue":"2","key":"117_CR20","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"I. Walukiewicz","year":"2001","unstructured":"Walukiewicz, I.: Pushdown processes: Games and model checking. Information and Computation\u00a0164(2), 234\u2013263 (2001)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_117.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:00Z","timestamp":1605643560000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11523468_117","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}