{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:29:34Z","timestamp":1743060574733,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030406073"},{"type":"electronic","value":"9783030406080"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-40608-0_20","type":"book-chapter","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:07:34Z","timestamp":1582589254000},"page":"287-299","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Cyclic Shift on Multi-component Grammars"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3877-4223","authenticated-orcid":false,"given":"Alexey","family":"Sorokin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,25]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-662-43742-1_5","volume-title":"Logical Aspects of Computational Linguistics","author":"A Clark","year":"2014","unstructured":"Clark, A., Yoshinaka, R.: An algebraic approach to multiple context-free grammars. In: Asher, N., Soloviev, S. (eds.) LACL 2014. LNCS, vol. 8535, pp. 57\u201369. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43742-1_5"},{"key":"20_CR2","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Adison-Wesley, Reading (1979)"},{"issue":"2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1051\/ita:2007038","volume":"42","author":"G Jir\u00e1skov\u00e1","year":"2008","unstructured":"Jir\u00e1skov\u00e1, G., Okhotin, A.: State complexity of cyclic shift. RAIRO-Theoret. Inform. Appl. 42(2), 335\u2013360 (2008)","journal-title":"RAIRO-Theoret. Inform. Appl."},{"issue":"1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/S0022-0000(75)80019-5","volume":"10","author":"AK Joshi","year":"1975","unstructured":"Joshi, A.K., Levy, L.S., Takahashi, M.: Tree adjunct grammars. J. Comput. Syst. Sci. 10(1), 136\u2013163 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR5","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. 5583, pp. 312\u2013325. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02737-6_25"},{"doi-asserted-by":"crossref","unstructured":"Kanazawa, M.: Ogden\u2019s lemma, multiple context-free grammars, and the control language hierarchy. Inf. Comput. (2019)","key":"20_CR6","DOI":"10.1016\/j.ic.2019.104449"},{"issue":"1","key":"20_CR7","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/s00224-014-9534-z","volume":"55","author":"M Kanazawa","year":"2014","unstructured":"Kanazawa, M., Kobele, G.M., Michaelis, J., Salvati, S., Yoshinaka, R.: The failure of the strong pumping lemma for multiple context-free languages. Theory Comput. Syst. 55(1), 250\u2013278 (2014)","journal-title":"Theory Comput. Syst."},{"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 (Volume 1: Long Papers), pp. 666\u2013674 (2012)","key":"20_CR8"},{"issue":"6","key":"20_CR9","first-page":"1266","volume":"194","author":"AN Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk 194(6), 1266\u20131268 (1970)","journal-title":"Dokl. Akad. Nauk"},{"issue":"4","key":"20_CR10","first-page":"81","volume":"9","author":"AN Maslov","year":"1973","unstructured":"Maslov, A.N.: Cyclic shift operation for languages. Problemy Peredachi Informatsii 9(4), 81\u201387 (1973)","journal-title":"Problemy Peredachi Informatsii"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2013.06.001","volume":"9","author":"A Okhotin","year":"2013","unstructured":"Okhotin, A.: Conjunctive and Boolean grammars: the true general case of the context-free grammars. Comput. Sci. Rev. 9, 27\u201359 (2013)","journal-title":"Comput. Sci. Rev."},{"issue":"4","key":"20_CR12","first-page":"119","volume":"55","author":"T Oshiba","year":"1972","unstructured":"Oshiba, T.: Closure property of family of context-free languages under cyclic shift operation. Electron. Commun. Jpn 55(4), 119\u2013122 (1972)","journal-title":"Electron. Commun. Jpn"},{"unstructured":"Pollard, C.J.: Generalized phrase structure grammars, head grammars, and natural language. Ph.D. dissertation, Stanford University (1984)","key":"20_CR13"},{"issue":"2","key":"20_CR14","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. Theoret. Comput. Sci. 88(2), 191\u2013229 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"20_CR15","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. 7734, pp. 319\u2013334. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-35722-0_23"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-319-27683-0_26","volume-title":"Logical Foundations of Computer Science","author":"A Sorokin","year":"2016","unstructured":"Sorokin, A.: Ogden property for linear displacement context-free grammars. In: Artemov, S., Nerode, A. (eds.) LFCS 2016. LNCS, vol. 9537, pp. 376\u2013391. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-27683-0_26"},{"issue":"1\u20133","key":"20_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2005.10.039","volume":"352","author":"V Terrier","year":"2006","unstructured":"Terrier, V.: Closure properties of cellular automata. Theoret. Comput. Sci. 352(1\u20133), 97\u2013107 (2006)","journal-title":"Theoret. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Vijay-Shanker, K., Weir, D.J., Joshi, A.K.: Characterizing structural descriptions produced by various grammatical formalisms. In: Proceedings of the 25th Annual Meeting on Association for Computational Linguistics, pp. 104\u2013111. Association for Computational Linguistics (1987)","key":"20_CR18","DOI":"10.3115\/981175.981190"},{"key":"20_CR19","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. 6031, pp. 596\u2013607. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13089-2_50"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-40608-0_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T20:42:25Z","timestamp":1741466545000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-40608-0_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030406073","9783030406080"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-40608-0_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Language and Automata Theory and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Milan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 March 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"lata2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/lata2020.irdta.eu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"In addition, there are 6 invited papers. Due to the coronavirus pandemic the actual conference was postponed to be held together with LATA 2021.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}