{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T22:10:23Z","timestamp":1741212623444,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642212536"},{"type":"electronic","value":"9783642212543"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-21254-3_10","type":"book-chapter","created":{"date-parts":[[2011,5,27]],"date-time":"2011-05-27T09:38:04Z","timestamp":1306489084000},"page":"142-154","source":"Crossref","is-referenced-by-count":10,"title":["Recognizing Shuffled Languages"],"prefix":"10.1007","author":[{"given":"Martin","family":"Berglund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henrik","family":"Bj\u00f6rklund","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johanna","family":"H\u00f6gberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"10_CR1","first-page":"205","volume":"11","author":"G.E. Barton","year":"1985","unstructured":"Barton, G.E.: On the complexity of ID\/LP parsing 1. Comput. Linguist.\u00a011(4), 205\u2013218 (1985)","journal-title":"Comput. Linguist."},{"key":"10_CR2","unstructured":"Berglund, M., Bj\u00f6rklund, H., H\u00f6gberg, J.: Recognizing shuffled languages. Technical Report UMINF 11.01, Computing Sci., Ume\u00e5 University (2011), http:\/\/www8.cs.umu.se\/research\/uminf\/index.cgi"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Biegler, F., Daley, M., McQuillan, I.: On the shuffle automaton size for words. In: DCFS, pp. 79\u201389 (2009)","DOI":"10.4204\/EPTCS.3.7"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1007\/978-3-540-74456-6_66","volume-title":"Mathematical Foundations of Computer Science 2007","author":"H. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Boja\u0144czyk, M.: Shuffle expressions and words with nested data. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 750\u2013761. Springer, Heidelberg (2007)"},{"issue":"1","key":"10_CR5","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1006\/inco.1997.2665","volume":"139","author":"S.B. Bloom","year":"1997","unstructured":"Bloom, S.B., \u00c9sik, Z.: Axiomatizing shuffle and concatenation in languages. Information and Comptuation\u00a0139(1), 62\u201391 (1997)","journal-title":"Information and Comptuation"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Muscholl, A., Schwentick, T., Segoufin, L., David, C.: Two-variable logic on words with data. In: Proc. LICS 2006, pp. 7\u201316 (2006)","DOI":"10.1109\/LICS.2006.51"},{"key":"10_CR7","first-page":"303","volume":"7","author":"C. C\u00e2mpeanu","year":"2002","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: Tight lower bound for the state complexity of shuffle of regular languages. J. Autom. Lang. Comb.\u00a07, 303\u2013310 (2002)","journal-title":"J. Autom. Lang. Comb."},{"issue":"1-2","key":"10_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1023\/A:1011118925938","volume":"11","author":"S. Carberry","year":"2001","unstructured":"Carberry, S.: Techniques for plan recognition. User Modeling and User-Adapted Interaction\u00a011(1-2), 31\u201348 (2001)","journal-title":"User Modeling and User-Adapted Interaction"},{"issue":"5","key":"10_CR9","first-page":"653","volume":"16","author":"M. Daley","year":"2010","unstructured":"Daley, M., Domaratzki, M., Salomaa, K.: Orthogonal concatenation: Language equations and state complexity. J. Universal Comp. Sci.\u00a016(5), 653\u2013675 (2010)","journal-title":"J. Universal Comp. Sci."},{"key":"10_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"6","key":"10_CR11","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/s002360050129","volume":"35","author":"Z. \u00c9sik","year":"1998","unstructured":"\u00c9sik, Z., Bertol, M.: Nonfinite axiomatizability of the equational theory of shuffle. Acta Informatica\u00a035(6), 505\u2013539 (1998)","journal-title":"Acta Informatica"},{"issue":"2","key":"10_CR12","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0304-3975(92)90339-H","volume":"96","author":"V. Garg","year":"1992","unstructured":"Garg, V., Ragunath, M.: Concurrent regular expressions and their relationship to petri nets. Theor. Comput. Sci.\u00a096(2), 285\u2013304 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10_CR13","first-page":"1486","volume":"39","author":"W. Gelade","year":"2009","unstructured":"Gelade, W., Martens, W., Neven, F.: Optimizing schema languages for XML: Numerical constraints and interleaving. SIAM J. on Comp.\u00a039(4), 1486\u20131530 (2009)","journal-title":"SIAM J. on Comp."},{"key":"10_CR14","volume-title":"The Mathematical Theory of Context Free Languages","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S.: The Mathematical Theory of Context Free Languages. McGraw-Hill, New York (1966)"},{"issue":"9","key":"10_CR15","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1145\/358746.358767","volume":"24","author":"J. Gischer","year":"1981","unstructured":"Gischer, J.: Shuffle languages, petri nets, and context-sensitive grammars. Comm. ACM\u00a024(9), 597\u2013605 (1981)","journal-title":"Comm. ACM"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"H\u00f6gberg, J., Kaati, L.: Weighted unranked tree automata as a framework for plan recognition. In: Proc. Fusion (2010) (to appear)","DOI":"10.1109\/ICIF.2010.5711969"},{"issue":"1-2","key":"10_CR17","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0304-3975(99)00109-7","volume":"250","author":"J. Jedrzejowicz","year":"2001","unstructured":"Jedrzejowicz, J., Szepietowski, A.: Shuffle languages are in P. Theor. Comput. Sci.\u00a0250(1-2), 31\u201353 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2004.09.038","volume":"332","author":"L. Kari","year":"2005","unstructured":"Kari, L., Sos\u00edk, P.: Aspects of shuffle and deletion on trajectories. Theor. Comput. Sci.\u00a0332, 47\u201361 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Kuhlmann, M., Satta, G.: Treebank grammar techniques for non-projective dependency parsing. In: Proc. EACL, pp. 478\u2013486 (2009)","DOI":"10.3115\/1609067.1609120"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00163-1","volume":"197","author":"A. Mateescu","year":"1998","unstructured":"Mateescu, A., Rozenberg, G., Salomaa, A.: Shuffle on trajectories: syntactic constraints. Theor. Comput. Sci.\u00a0197, 1\u201356 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1006\/inco.1994.1098","volume":"115","author":"A. Mayer","year":"1994","unstructured":"Mayer, A., Stockmeyer, L.: Word problems \u2013 this time with interleaving. Inform. and Comput.\u00a0115, 293\u2013311 (1994)","journal-title":"Inform. and Comput."},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Nivre, J.: Non-projective dependency parsing in expected linear time. In: Proc. ACL-IJCNLP 2009, pp. 351\u2013359 (2009)","DOI":"10.3115\/1687878.1687929"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Schmidt, C., Sridharan, N., Goodson, J.: The plan recognition problem: An intersection of psychology and artificial intelligence. A.I.\u00a011(1,2) (1978)","DOI":"10.1016\/0004-3702(78)90012-7"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21254-3_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T21:35:57Z","timestamp":1741210557000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21254-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642212536","9783642212543"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21254-3_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}