{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:11:00Z","timestamp":1725743460898},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642399978"},{"type":"electronic","value":"9783642399985"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39998-5_13","type":"book-chapter","created":{"date-parts":[[2013,7,30]],"date-time":"2013-07-30T01:59:20Z","timestamp":1375149560000},"page":"209-224","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of Free Word Orders"],"prefix":"10.1007","author":[{"given":"J\u00e9r\u00f4me","family":"Kirman","sequence":"first","affiliation":[]},{"given":"Sylvain","family":"Salvati","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"13_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF00289261","volume":"15","author":"T. Araki","year":"1981","unstructured":"Araki, T., Tokura, N.: Flow languages equal recursively enumerable languages. Acta Informatica\u00a015(3), 209\u2013217 (1981)","journal-title":"Acta Informatica"},{"key":"13_CR2","unstructured":"Becker, T., Rambow, O., Niv, M.: The derivational generative power of formal systems or scrambling is beyond LCFRS. Technical Report IRCS-92-38, UPENN (1992)"},{"issue":"1","key":"13_CR3","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., Kozen, D., Stockmeyer, L.: Alternation. JACM\u00a028(1), 114\u2013133 (1981)","journal-title":"JACM"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Dassow, J.: Grammars with regulated rewriting. In: Formal Languages and Applications, pp. 249\u2013273. Springer (2004)","DOI":"10.1007\/978-3-540-39886-8_13"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"de Groote, P.: Towards abstract categorial grammars. In: ACL (ed.). Proceedings 39th Annual Meeting and 10th Conference of the European Chapter, pp. 148\u2013155 (2001)","DOI":"10.3115\/1073012.1073045"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Gerdes, K., Kahane, S.: Word order in German: A formal dependency grammar using a topological hierarchy. In: ACL, pp. 220\u2013227 (2001)","DOI":"10.3115\/1073012.1073041"},{"issue":"4","key":"13_CR7","first-page":"379","volume":"35","author":"J. Jedrzejowicz","year":"2001","unstructured":"Jedrzejowicz, J., Szepietowski, A.: On the expressive power of the shuffle operator matched with intersection by regular sets. RAIRO\u00a035(4), 379\u2013388 (2001)","journal-title":"RAIRO"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Joshi, A.K.: Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions? In: Natural Language Parsing, pp. 206\u2013250. CUP (1985)","DOI":"10.1017\/CBO9780511597855.007"},{"issue":"1","key":"13_CR9","first-page":"78","volume":"75-D","author":"Y. Kaji","year":"1992","unstructured":"Kaji, Y., Nakanishi, R., Seki, H., Kasmi, T.: The universal recognition problems for multiple context-free grammars and for linear context-free rewriting systems. IEICE Trans. Inf. & Syst.\u00a0E 75-D(1), 78\u201388 (1992)","journal-title":"IEICE Trans. Inf. & Syst. E"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Kanazawa, M.: Abstract families of abstract categorial languages. In: 13th WoLLIC, ENTCS, pp. 65\u201380 (2006)","DOI":"10.1016\/j.entcs.2006.05.037"},{"issue":"2","key":"13_CR11","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10849-009-9109-6","volume":"19","author":"M. Kanazawa","year":"2010","unstructured":"Kanazawa, M.: Second-order abstract categorial grammars as hyperedge replacement grammars. Journal of Logic, Language and Information\u00a019(2), 137\u2013161 (2010)","journal-title":"Journal of Logic, Language and Information"},{"key":"13_CR12","unstructured":"Kanazawa, M., Salvati, S.: MIX is not a tree-adjoining language. In: Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers, vol.\u00a01, pp. 666\u2013674. ACL (2012)"},{"key":"13_CR13","unstructured":"Kuhlmann, M., M\u00f6hl, M.: Mildly context-sensitive dependency languages. In: ACL (2007)"},{"key":"13_CR14","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/11551874_18","volume-title":"Text, Speech and Dialogue","author":"M. Lopatkov\u00e1","year":"2005","unstructured":"Lopatkov\u00e1, M., Pl\u00e1tek, M., Kubo\u0148, V.: Modeling syntax of free word-order languages: Dependency analysis by reduction. In: Matou\u0161ek, V., Mautner, P., Pavelka, T. (eds.) TSD 2005. LNCS (LNAI), vol.\u00a03658, pp. 140\u2013147. Springer, Heidelberg (2005)"},{"issue":"3","key":"13_CR15","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s11168-007-9035-1","volume":"5","author":"R. Muskens","year":"2007","unstructured":"Muskens, R.: Separating syntax and combinatorics in categorial grammar. Research on Language and Computation\u00a05(3), 267\u2013285 (2007)","journal-title":"Research on Language and Computation"},{"issue":"4","key":"13_CR16","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R. Parikh","year":"1966","unstructured":"Parikh, R.: On context-free languages. JACM\u00a013(4), 570\u2013581 (1966)","journal-title":"JACM"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Rambow, O.: Multiset-valued linear index grammars: imposing dominance constraints on derivations. In: Proceedings of the 32nd Annual Meeting on Association for Computational Linguistics, pp. 263\u2013270. ACL (1994)","DOI":"10.3115\/981732.981768"},{"issue":"2","key":"13_CR18","first-page":"218","volume":"21","author":"W.L. Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. JCSS\u00a021(2), 218\u2013235 (1980)","journal-title":"JCSS"},{"key":"13_CR19","unstructured":"Salvati, S.: Probl\u00e8mes de filtrage et probl\u00e8me d\u2019analyse pour les grammaires cat\u00e9gorielles abstraites. PhD thesis, INPL (2005)"},{"key":"13_CR20","unstructured":"Salvati, S.: Mix is a 2-MCFL and the word problem in \u21242 is solved by a third-order collapsible pushdown automaton. Technical report, INRIA (2011)"},{"issue":"3","key":"13_CR21","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1109\/TSE.1978.231501","volume":"4","author":"A. Shaw","year":"1978","unstructured":"Shaw, A.: Software descriptions with flow expressions. IEEE Transactions on Software Engineering\u00a04(3), 242\u2013254 (1978)","journal-title":"IEEE Transactions on Software Engineering"},{"issue":"7","key":"13_CR22","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF00630810","volume":"2","author":"S. Shieber","year":"1984","unstructured":"Shieber, S.: Direct parsing of ID\/LP grammars. Linguistics and Philosophy\u00a02(7), 135\u2013154 (1984)","journal-title":"Linguistics and Philosophy"}],"container-title":["Lecture Notes in Computer Science","Formal Grammar"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39998-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T07:12:26Z","timestamp":1557990746000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39998-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642399978","9783642399985"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39998-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}