{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T15:34:36Z","timestamp":1774798476310,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662441152","type":"print"},{"value":"9783662441169","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44116-9_11","type":"book-chapter","created":{"date-parts":[[2014,7,10]],"date-time":"2014-07-10T03:50:37Z","timestamp":1404964237000},"page":"154-173","source":"Crossref","is-referenced-by-count":2,"title":["Monoid Automata for Displacement Context-Free Languages"],"prefix":"10.1007","author":[{"given":"Alexey","family":"Sorokin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Berstel, J.: Transductions and context-free languages, vol.\u00a04. Teubner Stuttgart (1979)","DOI":"10.1007\/978-3-663-09367-1"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.P.: The algebraic theory of context-free languages. computer programming and formal languages, pp. 118\u2013161. North-Holland (1963)","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"11_CR3","unstructured":"Fischer, M.J.: Grammars with macro-like productions. In: IEEE Conference Record of 9th Annual Symposium on Switching and Automata Theory, 1968, pp. 131\u2013142. IEEE (1968)"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Joshi, A.K.: Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? University of Pennsylvania, Moore School of Electrical Engineering, Department of Computer and Information Science (1985)","DOI":"10.1017\/CBO9780511597855.007"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Joshi, A.K., Schabes, Y.: Tree-adjoining grammars. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 69\u2013123. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_2"},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1080\/00927870802243580","volume":"37","author":"M. Kambites","year":"2009","unstructured":"Kambites, M.: Formal languages and groups as memory. Communications in Algebra\u00a037(1), 193\u2013208 (2009)","journal-title":"Communications in Algebra"},{"key":"11_CR7","unstructured":"Kanazawa, M.: A prefix-correct Earley recognizer for multiple context-free grammars. In: Proceedings of the Ninth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+ 9), pp. 49\u201356 (2008)"},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/978-3-642-02737-6_25","volume-title":"Developments in Language Theory","author":"M. Kanazawa","year":"2009","unstructured":"Kanazawa, M.: The pumping lemma for well-nested multiple context-free languages. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol.\u00a05583, pp. 312\u2013325. Springer, Heidelberg (2009)"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Kanazawa, M.: Multi-dimensional trees and a Chomsky-Sch\u00fctzenberger-Weir representation theorem for simple context-free tree grammars. Technical report (2013)","DOI":"10.1093\/logcom\/exu043"},{"key":"11_CR10","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. Association for Computational Linguistics (2012)"},{"issue":"1","key":"11_CR11","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.tcs.2005.11.024","volume":"354","author":"S. Kepser","year":"2006","unstructured":"Kepser, S., M\u00f6nnich, U.: Closure properties of linear context-free tree languages with an application to optimality theory. Theoretical Computer Science\u00a0354(1), 82\u201397 (2006)","journal-title":"Theoretical Computer Science"},{"key":"11_CR12","unstructured":"Lallement, G.: Semigroups and combinatorial applications. John Wiley & Sons, Inc. (1979)"},{"key":"11_CR13","first-page":"824","volume":"271","author":"M. Nivat","year":"1970","unstructured":"Nivat, M., Perrot, J.F.: Une g\u00e9n\u00e9ralisation du mono\u0131de bicyclique. CR Acad. Sci. Paris S\u00e9r. A\u00a0271, 824\u2013827 (1970)","journal-title":"CR Acad. Sci. Paris S\u00e9r. A"},{"key":"11_CR14","unstructured":"Pollard, C.: Generalized phrase structure grammars, head grammars, and natural languages. PhD thesis, Stanford University, Stanford (1984)"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Roach, K.: Formal properties of head grammars. Mathematics of Language, 293\u2013348 (1987)","DOI":"10.1075\/z.35.15roa"},{"key":"11_CR16","series-title":"Word, Language, Grammar","volume-title":"Handbook of formal languages","year":"1997","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of formal languages. Word, Language, Grammar, vol.\u00a01. Springer, New York (1997)"},{"issue":"2","key":"11_CR17","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1093\/ietisy\/e91-d.2.209","volume":"91","author":"H. Seki","year":"2008","unstructured":"Seki, H., Kato, Y.: On the generative power of multiple context-free grammars and macro grammars. IEICE Transactions on Information and Systems\u00a091(2), 209\u2013221 (2008)","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"2","key":"11_CR18","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","volume":"88","author":"H. Seki","year":"1991","unstructured":"Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoretical Computer Science\u00a088(2), 191\u2013229 (1991)","journal-title":"Theoretical Computer Science"},{"key":"11_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-35722-0_23","volume-title":"Logical Foundations of Computer Science","author":"A. Sorokin","year":"2013","unstructured":"Sorokin, A.: Normal forms for multiple context-free languages and displacement Lambek grammars. In: Artemov, S., Nerode, A. (eds.) LFCS 2013. LNCS, vol.\u00a07734, pp. 319\u2013334. Springer, Heidelberg (2013)"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Vijay-Shanker, K., Weir, D.J., Joshi, A.K.: Tree adjoining and head wrapping. In: Proceedings of the 11th coference on Computational linguistics, pp. 202\u2013207. Association for Computational Linguistics (1986)","DOI":"10.3115\/991365.991425"},{"key":"11_CR21","unstructured":"Weir, D.J.: Characterizing mildly context-sensitive grammar formalisms. PhD thesis, University of Pennsylvania (1988)"},{"key":"11_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1007\/978-3-642-13089-2_50","volume-title":"Language and Automata Theory and Applications","author":"R. Yoshinaka","year":"2010","unstructured":"Yoshinaka, R., Kaji, Y., Seki, H.: Chomsky-sch\u00fctzenberger-type characterization of multiple context-free languages. In: Dediu, A.-H., Fernau, H., Mart\u00edn-Vide, C. (eds.) LATA 2010. LNCS, vol.\u00a06031, pp. 596\u2013607. Springer, Heidelberg (2010)"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-642-22012-8_17","volume-title":"Automata, Languages and Programming","author":"G. Zetzsche","year":"2011","unstructured":"Zetzsche, G.: On the capabilities of grammars, automata, and transducers controlled by monoids. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 222\u2013233. Springer, Heidelberg (2011)"},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/978-3-642-39212-2_39","volume-title":"Automata, Languages, and Programming","author":"G. Zetzsche","year":"2013","unstructured":"Zetzsche, G.: Silent transitions in automata with storage. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol.\u00a07966, pp. 434\u2013445. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Pristine Perspectives on Logic, Language, and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44116-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,22]],"date-time":"2020-08-22T03:49:25Z","timestamp":1598068165000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44116-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662441152","9783662441169"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44116-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}